We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check If N and Its Double Exist

Number: 1468

Difficulty: Easy

Paid? No

Companies: Google, Bloomberg, Amazon

Problem Description

Given an array of integers, determine whether there exist two distinct indices i and j such that arr[i] is double arr[j].

Key Insights

  • Use a hash set to track numbers seen so far.
  • For every number x in the array, check if 2*x is in the set.
  • Additionally, if x is even, check if x/2 is in the set.
  • This one-pass method handles zero and negative numbers without special cases.
  • Alternatively, sorting combined with two pointers is possible but less efficient.

Space and Time Complexity

Time Complexity: O(n) since we iterate through the array once. Space Complexity: O(n) due to the hash set used for storing seen numbers.

Solution

We iterate through the array while storing each number in a hash set. For each number, we check if either its double or, if it is even, its half already exists in the set. This ensures that we efficiently detect any pair satisfying arr[i] == 2 * arr[j]. The solution handles edge cases such as the number 0 (since 0 == 2 * 0) and negative numbers seamlessly.

Code Solutions

def checkIfExist(arr):
    # Initialize an empty set to store seen numbers.
    seen = set()
    # Iterate through each number in the array.
    for num in arr:
        # Check if double of the number is in the seen set.
        if (2 * num) in seen:
            return True
        # If the number is even, check if half of it is in the seen set.
        if num % 2 == 0 and (num // 2) in seen:
            return True
        # Add the current number to the set.
        seen.add(num)
    return False

# Example usage:
if __name__ == "__main__":
    arr = [10, 2, 5, 3]
    print(checkIfExist(arr))  # Output: True
← Back to All Questions