LeetCode 1346. Check If N and Its Double Exist Solution in Java, C++, Python & More | Explanation + Code

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.

PythonJavaC++GoTypeScript

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(code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)

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; }(code-box)