Elements in the Range

Problem

Given an array arr[] containing positive elements. A and B are two numbers defining a range. The task is to check if the array contains all elements in the given range.

Examples:

Example 1:

Input: N = 7, A = 2, B = 5
arr[] =  {1, 4, 5, 2, 7, 8, 3}
Output: Yes
Explanation: It has elements between range 2-5 i.e 2,3,4,5

Example 2:

Input: N = 7, A = 2, B = 6
arr[] = {1, 4, 5, 2, 7, 8, 3}
Output: No
Explanation: Array does not contain 6.

Your task:

This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function check_elements() that takes array arr, integer N, integer A, and integer B as parameters and returns the boolean True if array elements contain all elements in the given range else boolean False.

Note: If the array contains all elements in the given range then driver code outputs Yes otherwise, it outputs No

• Expected Time Complexity: $O(N)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^7$

Solution

Python

def check_elements(self, arr, n, A, B):
    rangeV = B - A
    for i in range(0, n):
        if A <= abs(arr[i]) <= B:
            z = abs(arr[i]) - A
            if 0 <= z < n and arr[z] > 0:
                arr[z] = arr[z] * -1
    count = 0
    for i in range(0, rangeV + 1):
        if i >= n:
            break
        if arr[i] > 0:
            return False
        else:
            count += 1
    if count != (rangeV + 1):
        return False
    return True

Java

boolean check_elements(int arr[], int n, int A, int B) {
    int rangeV = B - A;
    for (int i = 0; i < n; i++) {
        if (Math.abs(arr[i]) >= A && Math.abs(arr[i]) <= B) {
            int z = Math.abs(arr[i]) - A;
            if (z >= 0 && z < n && arr[z] > 0) {
                arr[z] = arr[z] * -1;
            }
        }
    }
    int count = 0;
    for (int i = 0; i <= rangeV; i++) {
        if (i >= n) {
            break;
        }
        if (arr[i] > 0) {
            return false;
        } else {
            count++;
        }
    }
    
    if (count != (rangeV + 1)) {
        return false;
    }
    return true;
}

C++

bool check_elements(int arr[], int n, int A, int B) {
	int rangeV = B - A;
    for (int i = 0; i < n; i++) {
        if (abs(arr[i]) >= A && abs(arr[i]) <= B) {
            int z = abs(arr[i]) - A;
            if (z >= 0 && z < n && arr[z] > 0) {
                arr[z] = arr[z] * -1;
            }
        }
    }
    int count = 0;
    for (int i = 0; i <= rangeV; i++) {
        if (i >= n) {
            break;
        }
        if (arr[i] > 0) {
            return false;
        } else {
            count++;
        }
    }
    if (count != (rangeV + 1)) {
        return false;
    }
    return true;
}

C

bool check_elements(int arr[], int n, int A, int B) {
    int rangeV = B - A;
    for (int i = 0; i < n; i++) {
        if (abs(arr[i]) >= A && abs(arr[i]) <= B) {
            int z = abs(arr[i]) - A;
            if (z >= 0 && z < n && arr[z] > 0) {
                arr[z] = arr[z] * -1;
            }
        }
    }
    int count = 0;
    for (int i = 0; i <= rangeV; i++) {
        if (i >= n) {
            break;
        }
        if (arr[i] > 0) {
            return false;
        } else {
            count++;
        }
    }
    if (count != (rangeV + 1)) {
        return false;
    }
    return true;
}

• Time Complexity: $O(N)$
• Auxiliary Space: $O(1)$