Objective: Given an array of unsorted numbers, check if it contains all elements of some given range.
Examples:
int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 };
Range : 12-15
Output: True
Approach:
Naive Approach: Sorting . Time Complexity – O(nlogn).
Better Approach: Time Complexity – O(n).
- Find the range = y-x;
- Do the linear scan of array.
- Check if element falls within the range of x and y, (arrA[i]>=x && arrA[i]<=y)
- If Yes then calculate z = arrA[i]-x;
- Make the arrA[z] element as negative.
- Once the linear scan is done, just check all the elements in arrA[] from 0 to range are negative, if yes them array contains all the numbers of the given range, return true, else false.
- See the Picture below for better explanation
Complete Code:
| public class CheckArrayContainsAllElementsInGivenRange { | |
| public Boolean find(int[] arrA, int x, int y) { | |
| int range = y – x; | |
| for (int i = 0; i < arrA.length; i++) { | |
| if (arrA[i] >= x && arrA[i] <= y) { | |
| int z = arrA[i] – x; | |
| if (arrA[z] > 0) { | |
| arrA[z] = arrA[z] * –1; | |
| } | |
| } | |
| } | |
| // for(int i=0;i<arrA.length;i++){ | |
| // System.out.print(" " + arrA[i]); | |
| // } | |
| for (int i = 0; i < range; i++) { | |
| if (arrA[i] > 0) | |
| return false; | |
| } | |
| return true; | |
| } | |
| public static void main(String[] args) throws java.lang.Exception { | |
| int[] arrA = { 11, 17, 13, 19, 15, 16, 12, 14 }; | |
| int x = 12; | |
| int y = 15; | |
| CheckArrayContainsAllElementsInGivenRange i = new CheckArrayContainsAllElementsInGivenRange(); | |
| System.out.println(i.find(arrA, x, y)); | |
| } | |
| } |
Output:
True