Check If N and Its Double Exist

Difficulty: Easy | Acceptance: 41.80% | Paid: No Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

Given an array arr of integers, check if there exists two indices i and j such that :

i != j and arr[i] == 2 * arr[j].

• Examples
• Constraints
• Brute Force
• Hash Set
• Sorting + Binary Search

Examples

Example 1

Input:

arr = [10,2,5,3]

Output:

true

Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2

Input:

arr = [3,1,7,11]

Output:

false

Explanation: There is no i and j that satisfy the conditions.

Constraints

2 <= arr.length <= 500
-10³ <= arr[i] <= 10³

Brute Force

Intuition Check every possible pair of indices (i, j) in the array to see if the condition arr[i] == 2 * arr[j] is met, ensuring i != j.

Steps

• Iterate through the array with index i.
• For each i, iterate through the array with index j.
• If i != j and arr[i] == 2 * arr[j], return true.
• If loops finish without finding a match, return false.

class Solution:
    def checkIfExist(self, arr):
        n = len(arr)
        for i in range(n):
            for j in range(n):
                if i != j and arr[i] == 2 * arr[j]:
                    return True
        return False

Complexity

• Time: O(n²)
• Space: O(1)
• Notes: Simple but inefficient for large arrays.

Hash Set

Intuition Use a hash set to store numbers we have seen so far. For each number x, check if 2*x or x/2 (if x is even) already exists in the set.

Steps

• Initialize an empty hash set.
• Iterate through each number x in the array.
• Check if 2*x is in the set, or if x is even and x/2 is in the set.
• If yes, return true.
• Add x to the set.
• If the loop finishes, return false.

class Solution:
    def checkIfExist(self, arr):
        seen = set()
        for n in arr:
            if 2 * n in seen or (n % 2 == 0 and n // 2 in seen):
                return True
            seen.add(n)
        return False

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Most efficient time complexity, uses extra space for the set.

Sorting + Binary Search

Intuition Sort the array first. For each element arr[i], perform a binary search for 2 * arr[i] in the rest of the array (i+1 to end).

Steps

• Sort the array in ascending order.
• Iterate through the array with index i.
• Calculate target = 2 * arr[i].
• Perform binary search for target in the subarray arr[i+1…n-1].
• If found, return true.
• If loop finishes, return false.

class Solution:
    def checkIfExist(self, arr):
        arr.sort()
        n = len(arr)
        for i in range(n):
            target = 2 * arr[i]
            left, right = i + 1, n - 1
            while left <= right:
                mid = (left + right) // 2
                if arr[mid] == target:
                    return True
                elif arr[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
        return False

Complexity

• Time: O(n log n)
• Space: O(1) or O(n) depending on sorting implementation
• Notes: Good balance if space is constrained, though slower than Hash Set.