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:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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