Check If N and Its Double Exist — Problem & Solution
Check If N and Its Double Exist solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Check If N and Its Double Exist is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Two Pointers
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an array arr of integers, return true if there exist two distinct indices i and j such that arr[i] == 2 * arr[j].
Example 1
Input: arr = [10,2,5,3]
Output: true
Explanation: 10 = 2 × 5.
Example 2
Input: arr = [3,1,7,11]
Output: false
Example 3
Input: arr = [0,0]
Output: true
Explanation: 0 = 2 × 0, and the two zeros sit at different indices.
Constraints
2 <= arr.length <= 40-1000 <= arr[i] <= 1000
Hints for Check If N and Its Double Exist
Hint 1
A hash set of seen values turns this into one pass: for each
x, look for2xand forx / 2.Hint 2
Only check
x / 2whenxis even, or you will match a value that is not actually present.Hint 3
Zero is the trap: it needs a second zero, not just itself.
How to solve Check If N and Its Double Exist
Scan with a set of seen values, checking for both 2x and x / 2 (only when x is even).
Approach
- For each
x, returntrueif2xis in the set, orxis even andx / 2is in the set. - Add
xto the set.
Why it works
A valid pair (i, j) is discovered when the later of the two is scanned, whichever role it plays; checking before inserting prevents x from matching itself.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Zero needs a second zero — the check-before-insert order gets this right automatically.
- Checking
x / 2for oddxin integer arithmetic matches a value that is not actually the half.
Reference solution
Python
def checkIfExist(arr) -> bool:
seen = set()
for x in arr:
if 2 * x in seen or (x % 2 == 0 and x // 2 in seen):
return True
seen.add(x)
return FalseJava
public static boolean checkIfExist(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int x : arr) {
if (seen.contains(2 * x)) return true;
if (x % 2 == 0 && seen.contains(x / 2)) return true;
seen.add(x);
}
return false;
}C++
bool checkIfExist(vector<int>& arr) {
unordered_set<int> seen;
for (int x : arr) {
if (seen.count(2 * x)) return true;
if (x % 2 == 0 && seen.count(x / 2)) return true;
seen.insert(x);
}
return false;
}JavaScript
var checkIfExist = function(arr) {
const seen = new Set();
for (let i = 0; i < arr.length; i++) {
const x = arr[i];
if (seen.has(2 * x) || (x % 2 === 0 && seen.has(x / 2))) return true;
seen.add(x);
}
return false;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets