1346. Check If N and Its Double Exist - Detailed Explanation

Problem Statement

You are given an array of integers, arr. The task is to determine whether there exists two distinct indices i and j such that:

[ \text{arr}[i] = 2 \times \text{arr}[j] ]

Return true if such a pair exists; otherwise, return false.

Example 1

• Input: [10, 2, 5, 3]
• Output: true
• Explanation:
  For this array, 10 is exactly double 5. Therefore, the condition is satisfied.

Example 2

• Input: [7, 1, 14, 11]
• Output: true
• Explanation:
  In this case, 14 is double 7, so the answer is true.

Example 3

• Input: [3, 1, 7, 11]
• Output: false
• Explanation:
  No element in this array is double another element, so the answer is false.

Constraints

• (2 \leq \text{arr.length} \leq 500)
• (-10^3 \leq \text{arr}[i] \leq 10^3)

Note:
Special attention is required for the value 0 because if there are at least two zeros in the array, then 0 is considered double of 0.

Hints to Guide Your Approach

1. Use a Hash Set or Frequency Map:
   Since you need to quickly check whether a value (or its half) exists, a hash set (or frequency map) is an excellent choice.

   • For each number n, check if 2 * n is already seen.
   • Also, if n is even, check if n / 2 is in the set.
     This way, you cover both cases where n might be the double or the half of another number.

2. Handling Zero:
   When n is 0, since (0 = 2 \times 0), ensure that the algorithm correctly identifies that at least two 0s must be present.

Approaches to Solve the Problem

Approach 1: Hash Set / Frequency Map Method (Optimal)

Explanation

• Idea:
  Traverse through the array while maintaining a hash set (or frequency map) of numbers encountered so far. For every element n, check whether:

  • 2 * n exists in the set, or
  • If n is even, whether n / 2 exists in the set.

• Steps:

  1. Initialize an empty set.
  2. Iterate over each number n in the array.
  3. Check if 2 * n or (if n is even) n / 2 is in the set.
  4. If found, return true immediately.
  5. Otherwise, add n to the set.
  6. If no valid pair is found after processing all elements, return false.

• Handling Special Case (0):
  When processing 0, the check ensures that if another 0 is found later (or if 0 is already in the set), the function returns true.

Complexity Analysis

• Time Complexity: (O(n)), since each element is processed once.
• Space Complexity: (O(n)), to store the elements in the hash set.

Approach 2: Sorting and Binary Search

Explanation

• Idea:
  First, sort the array. Then, for each element, perform a binary search for its double.

• Steps:

  1. Sort the array.
  2. For each element n in the sorted array, perform a binary search to look for 2 * n.
  3. Return true if found (ensuring that the indices are different).
  4. If no such pair exists, return false.

• Note:
  This approach runs in (O(n \log n)) due to the sort and binary search steps and is slightly less efficient than the hash set approach for this problem.

Complexity Analysis

• Time Complexity: (O(n \log n))
• Space Complexity: (O(1)) or (O(n)) if sorting requires additional space.

4. Code Implementations

Python Code

Below is the Python implementation using the hash set approach: