Check If N and Its Double Exist

Problem Statement

In this problem, you are provided with an array of integers arr. The task is to determine if there are two distinct indices i and j in the array such that the value at index i is double the value at index j. More formally, the conditions to satisfy are:

• the indices i and j should be different (i != j),
• both indices must be valid within the array bounds (0 <= i, j < arr.length),
• and the value at i should be exactly twice the value at j (arr[i] == 2 * arr[j]).

Understanding whether such a pair (i, j) exists in the array based on the given conditions would effectively address the problem.

Examples

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

Approach and Intuition

The given problem revolves around finding a particular relationship between two array elements denoted by their indices. Given the constraints and properties, here's an intuitive approach to solve it:

1. Traverse through the array using a loop where each element is considered as potential arr[j].
2. Inside this loop, run another loop to check each other element in the array that could be arr[i] (where arr[i] == 2 * arr[j]).
3. Keeping track of already seen numbers could greatly improve the efficiency. For this purpose, employing a hash map (or hash set) to store numbers that have already been checked can be helpful because:
   • You can look up the existence of the required doubled value (or half value, depending on which is smaller and which is already seen) in constant time.
4. Continue this process throughout the array. If at any point, a valid (i, j) pair is found that satisfies arr[i] == 2 * arr[j], return true.
5. If the end of the array is reached without finding such a pair, then return false.

This method ensures that each potential pair is checked efficiently, respecting the constraints provided, which specify an array length up to 500 elements, ensuring the approach will run effectively within these bounds.

Solutions

class Solution {
public:
    bool hasPairWithDouble(vector<int>& nums) {
        unordered_map<int, int> countMap;
    
        // Populate counts of each number
        for (int value : nums) {
            countMap[value]++;
        }
    
        for (int value : nums) {
            // Check if there's a double of the current element
            if (value != 0 && countMap.find(value * 2) != countMap.end()) {
                return true;
            }
            // Special case for zero to have two occurrences
            if (value == 0 && countMap[value] > 1) {
                return true;
            }
        }
        return false;
    }
};