Check If N and Its Double Exist

Leetcode Problem:

• Check If N and Its Double Exist

Summary

• Check if there exist two indices i and j in the given array such that arr[i] == 2 * arr[j] and i!= j.

Approach

• The approach used is to use a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array.

Complexity

• O(n) where n is the size of the array

Explanation

• The given solution uses a boolean array of size 4004 to keep track of the numbers we have seen so far
• For each number in the array, we check if its double or half exists in the boolean array
• If it does, we return true
• If not, we mark the number as seen in the boolean array
• The time complexity of this solution is O(n) where n is the size of the array, as we are iterating through the array once
• The space complexity is also O(n) as we are using a boolean array of size 4004 to keep track of the numbers we have seen so far.

Solution Code:

class Solution {
public:
    int number[4004];
    bool checkIfExist(vector& arr) {
        for(int i = 0 ; i < arr.size(); i++){
            if (arr[i] & 1) {
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
            } else{
                if(number[(arr[i] << 1) + 2000]){
                    return true;
                }
                if(number[(arr[i] >> 1) + 2000]){
                    return true;
                }
            }
            number[arr[i] + 2000] = true;
        }
        return false;
    }
};