Domain 1EasyCORE

Check If N and Its Double Exist

The problem asks us to determine if there exist two integers `N` and `M` in an array such that `N` is exactly double `M`. Specifically, we need to find indices `i` and `j` where `arr[i] == 2 * arr[j]`, with the constraint that `i != j`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1346. Check If N and Its Double Exist

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 36.0%


Problem Breakdown

The problem asks us to determine if there exist two integers N and M in an array such that N is exactly double M. Specifically, we need to find indices i and j where arr[i] == 2 * arr[j], with the constraint that i != j.

Inputs:

  • An array of integers arr.

Outputs:

  • A boolean value indicating whether such a pair exists.

Implicit Constraints or Edge Cases:

  • The array can contain negative numbers.
  • Duplicates are allowed, which could affect the solution approach.
  • The array length is between 2 and 500, so an efficient solution should consider time complexity.

Intuition

A brute-force approach would involve checking every pair of elements in the array to see if one is double the other. This would result in a time complexity of O(n^2), which is inefficient given the constraints.

The key insight is to use a hash map (or dictionary) to store each element and its index as we iterate through the array. This allows us to check in constant time whether the double or half of the current element exists in the array, reducing the overall complexity to O(n).

Approach

  1. Initialize an empty dictionary num_map to store numbers and their indices.
  2. Iterate through each number num in the array:
    • Check if num * 2 is already in num_map. If it is, return True.
    • Check if num / 2 (using integer division) is already in num_map and ensure that the original number was not zero to avoid false positives. If both conditions are met, return True.
    • Add the current number num and its index to num_map.
  3. If no such pair is found after iterating through the array, return False.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the array. We make a single pass through the array, performing constant-time operations for each element.
  • Space Complexity: O(n) in the worst case, where all elements are stored in the dictionary.

Solution

def checkIfExist(arr):
    num_map = {}
    
    for num in arr:
        if num * 2 in num_map or (num % 2 == 0 and num // 2 in num_map):
            return True
        num_map[num] = True
    
    return False

Edge Cases Handled

  • Negative Numbers: The solution correctly handles negative numbers by checking both num * 2 and num / 2.
  • Duplicates: Duplicates are handled naturally by the dictionary, as we only need to find one occurrence of the double or half.
  • Zero: The condition (num % 2 == 0 and num // 2 in num_map) ensures that zero is not incorrectly matched with itself.