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
- Initialize an empty dictionary
num_mapto store numbers and their indices. - Iterate through each number
numin the array:- Check if
num * 2is already innum_map. If it is, returnTrue. - Check if
num / 2(using integer division) is already innum_mapand ensure that the original number was not zero to avoid false positives. If both conditions are met, returnTrue. - Add the current number
numand its index tonum_map.
- Check if
- 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 * 2andnum / 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.