{x}
blog image

Check If N and Its Double Exist

Given an array arr of integers, check if there exist two indices i and j such that :

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

 

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

 

Constraints:

  • 2 <= arr.length <= 500
  • -103 <= arr[i] <= 103

Solution Explanation: Check If N and Its Double Exist

The problem asks to determine if an array contains two numbers where one is double the other. The most efficient approach uses a hash table (or set in many languages) to achieve linear time complexity.

Algorithm:

  1. Initialize a Hash Table (Set): Create an empty hash table (or set) to store the numbers encountered so far. A set is preferred because it offers constant-time lookups (contains operation).

  2. Iterate Through the Array: Traverse the input array arr. For each number x:

    • Check for Double or Half: Check if either 2 * x or x / 2 (only if x is even) is already present in the hash table. If either is found, it means we've found a pair satisfying the condition, so return true.

    • Add to Hash Table: If neither double nor half is found, add x to the hash table.

  3. Return False: If the loop completes without finding such a pair, return false.

Time Complexity Analysis:

  • The hash table lookup (contains operation) takes O(1) on average.
  • The array traversal takes O(n), where n is the length of the array.
  • Therefore, the overall time complexity is O(n).

Space Complexity Analysis:

  • The hash table stores at most n elements (in the worst case, all unique numbers).
  • Therefore, the space complexity is O(n).

Code Examples (with explanations):

Python:

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        seen = set()  # Use a set for efficient lookups
        for num in arr:
            if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
                return True  # Found a pair
            seen.add(num)  # Add the number to the set
        return False  # No pair found

Java:

import java.util.HashSet;
import java.util.Set;
 
class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int num : arr) {
            if (seen.contains(2 * num) || (num % 2 == 0 && seen.contains(num / 2))) {
                return true;
            }
            seen.add(num);
        }
        return false;
    }
}

C++:

#include <unordered_set>
#include <vector>
 
class Solution {
public:
    bool checkIfExist(std::vector<int>& arr) {
        std::unordered_set<int> seen;
        for (int num : arr) {
            if (seen.count(2 * num) || (num % 2 == 0 && seen.count(num / 2))) {
                return true;
            }
            seen.insert(num);
        }
        return false;
    }
};

Go:

func checkIfExist(arr []int) bool {
	seen := make(map[int]bool)
	for _, num := range arr {
		if seen[2*num] || (num%2 == 0 && seen[num/2]) {
			return true
		}
		seen[num] = true
	}
	return false
}

Javascript:

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var checkIfExist = function(arr) {
    const seen = new Set();
    for (const num of arr) {
        if (seen.has(2 * num) || (num % 2 === 0 && seen.has(num / 2))) {
            return true;
        }
        seen.add(num);
    }
    return false;
};

All these code snippets follow the same algorithmic approach, leveraging the efficiency of hash tables (or sets) to achieve a linear time solution. The minor syntax differences reflect the peculiarities of each programming language.