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

Check if Array Contains All Elements Of Some Given Range

Complete Code:

Output:

True

__________________________________________________ Top Companies Interview Questions..-

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

# check for only items between our range
if item >= start and item <= end:
# if we find an item IE; 12 we need to mark it
# as visited in our array, so 12-12 = 0, so it
# goes it slot 0, 13 goes in slot 1, 13-12 1 etc...
visited[item-start] = True

# return True if all were visited
return all(visited)