Check If N and Its Double Exist – 1346. LeetCode

The problem “Check If N and Its Double Exist” asks us to determine if there exists an integer  n  in the array such that  n  and  2 \times n  are both present in the array.

Example:

• Input: [10, 2, 5, 3]

• Output: true (since  n = 5  and  2 \times n = 10 )

This problem emphasizes searching efficiently within an array, leveraging appropriate data structures to minimize time complexity.

Brute Force Approach

public class CheckIfDoubleExist {
    public boolean checkIfExist(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (i != j && arr[i] == 2 * arr[j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

1. Iterate through every pair of elements.

2. Check if one element is double the other.

3. Return true if such a pair is found; otherwise, return false.

Optimized Approach

Algorithm and Data Structure

1. Use a HashSet to efficiently store and lookup elements.

2. Traverse the array once, checking for:

• 2 x n : If  n  exists and  2 x n  is already in the set.

• n / 2 : If  n  is even and its half exists in the set.

3. Add each number to the set for future lookups.

Why This Works

• A HashSet provides  O(1)  average-time complexity for insert and lookup operations.

• By traversing the array only once and leveraging the set, the algorithm avoids nested loops.

import java.util.HashSet;

public class CheckIfDoubleExist {
    public boolean checkIfExist(int[] arr) {
        HashSet<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;
    }
}

Line-By-Line Explanation

Step 1: Initialization

HashSet<Integer> seen = new HashSet<>();

• Create a set to store elements for efficient lookups

Step 2: Iterate Through the Array

for (int num : arr) {

• Traverse each element in the array.

Step 3: Check Conditions

if (seen.contains(2 * num) || (num % 2 == 0 && seen.contains(num / 2))) {
    return true;
}

• Checks if 2 x num already exists in the set.
• Checks if 2 / num already exists in the set. Used to detect the “double relationship” between the current numner and a number that has already been added to the set.

Step 4: Add to the set

seen.add(num);

• Add the current number to the set for future lookups.

Step 5: Default Return

return false;

• If no valid pair is found after traversing the array, return false.

Why This Code Works

The “Check If N and Its Double Exist” problem emphasizes efficient search within arrays using hash-based lookups. By leveraging sets and constant-time operations, the optimized solution is significantly faster and more scalable than brute force. Understanding the relationships between elements and choosing the right data structures (like HashSet) highlights the importance of algorithm design in solving real-world problems.