1346.check-if-n-and-its-double-exist.md

1346. Check If N and Its Double Exist

Test Cases

Normal Cases

Input: [10, ..., 5, ...]
Output: true

Input: [7, 1, 2]
Output: false

Edge / Corner Cases

• The array contains the same number more than once.

Input: [8, 1, 2, 8, 9]
Output: false

• The number is negative.

Input: [-10, 1, -20, 5]
Output: true

• There is one 0's or multiple 0's.

Input: [0, 1, 2, 0]
Output: true

Input: [3, 2, 0, 5]
Output: false

Hash Set

We iterate every number and check if it's double or half is in the set.

fun checkIfExist(arr: IntArray): Boolean {
    val set = HashSet<Int>()
    for (num in arr) {
        if (num * 2 in set) return true
        // We have to ensure the number is even before check.
        if (num % 2 == 0 && num / 2 in set) return true
        set.add(num)
    }
    return false
}

A common pitfall is to check only num * 2 in the set, but forget to check num / 2 if the number is even. Failed test case: [7, ..., 14, ...], 14 is checked before we add it to the set and we don't check if 14 / 2 exists in the set.

fun checkIfExist(arr: IntArray): Boolean {
    val set = HashSet<Int>()
    for (num in arr) {
        if (num * 2 in set) return true
        set.add(num)
    }
    return false
}

• Time Complexity: O(n)
• Space Complexity: O(n)

Binary Search

We can sort the array, and iterate each number to find its double using binary search. Please note that the edge cases

1. T he number is 0 and its double is also 0.

fun checkIfExist(arr: IntArray): Boolean {
    arr.sort()
    for (i in arr.indices) {
        val num = arr[i]
        val foundIndex = binarySearch(arr, num * 2)
        if (foundIndex != -1 && foundIndex != i) return true
    }
    return false
}

private fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        if (arr[middle] == target) return middle
        if (arr[middle] < target) left = middle + 1
        else right = middle - 1
    }
    return -1 // Not found
}

• Time Complexity: O(n log n)
• Space Complexity: O(log n)