Problem of The Day: Check If N and Its Double Exist

Problem Statement

My Solution

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        hash_map = defaultdict(list)
        for i, x in enumerate(arr):
            hash_map[x].append(i)
        for i, x in enumerate(arr):
            if x * 2 in hash_map:
                if x != x * 2:
                    return True
                for j in hash_map[x]:
                    if j != i:
                        return True
        return False

Editorial

Approach 1: Brute Force

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        # Step 1: Iterate through all pairs of indices
        for i in range(len(arr)):
            for j in range(len(arr)):
                # Step 2: Check the conditions
                if i != j and arr[i] == 2 * arr[j]:
                    return True
        # No valid pair found
        return False

Approach 2: Set Lookup

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        seen = set()
        for num in arr:
            # Check if 2 * num or num / 2 exists in the set
            if 2 * num in seen or (num % 2 == 0 and num // 2 in seen):
                return True
            # Add the current number to the set
            seen.add(num)
        # No valid pair found
        return False

Approach 3: Sorting + Binary Search

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        # Step 1: Sort the array
        arr.sort()

        for i in range(len(arr)):
            # Step 2: Calculate the target (double of current number)
            target = 2 * arr[i]
            # Step 3: Custom binary search for the target
            index = self._custom_binary_search(arr, target)
            # If the target exists and is not the same index
            if index >= 0 and index != i:
                return True
        # No valid pair found
        return False

    def _custom_binary_search(self, arr: List[int], target: int) -> int:
        left, right = 0, len(arr) - 1

        while left <= right:
            # Avoid potential overflow
            mid = left + (right - left) // 2

            if arr[mid] == target:
                return mid
            elif arr[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return -1  # Target not found

Approach 4: Frequency Hash Map

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        count = {}

        # Count occurrences of each number
        for num in arr:
            count[num] = count.get(num, 0) + 1

        for num in arr:
            # Check for double
            if num != 0 and 2 * num in count:
                return True
            # Handle zero case (ensure there are at least two zeros)
            if num == 0 and count[num] > 1:
                return True

        return False