Skip to content

1346. Check If N and Its Double Exist

Description

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

  • i != j
  • 0 <= i, j < arr.length
  • arr[i] == 2 * arr[j]

 

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
  • -103 <= arr[i] <= 103

Solutions

Solution 1: Hash Table

We define a hash table \(s\) to record the elements that have been visited.

Traverse the array \(arr\). For each element \(x\), if either double of \(x\) or half of \(x\) is in the hash table \(s\), then return true. Otherwise, add \(x\) to the hash table \(s\).

If no element satisfying the condition is found after the traversal, return false.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(arr\).

1
2
3
4
5
6
7
8
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        s = set()
        for x in arr:
            if x * 2 in s or (x % 2 == 0 and x // 2 in s):
                return True
            s.add(x)
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> s = new HashSet<>();
        for (int x : arr) {
            if (s.contains(x * 2) || ((x % 2 == 0 && s.contains(x / 2)))) {
                return true;
            }
            s.add(x);
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s;
        for (int x : arr) {
            if (s.contains(x * 2) || (x % 2 == 0 && s.contains(x / 2))) {
                return true;
            }
            s.insert(x);
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
func checkIfExist(arr []int) bool {
    s := map[int]bool{}
    for _, x := range arr {
        if s[x*2] || (x%2 == 0 && s[x/2]) {
            return true
        }
        s[x] = true
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
function checkIfExist(arr: number[]): boolean {
    const s: Set<number> = new Set();
    for (const x of arr) {
        if (s.has(x * 2) || (x % 2 === 0 && s.has((x / 2) | 0))) {
            return true;
        }
        s.add(x);
    }
    return false;
}

Comments