Check If N and Its Double Exist

Easy
258.

Check If N and Its Double Exist

Check If N and Its Double Exist is an easy coding problem on arrays, hash table and sorting, asked in Amazon and Adobe interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var checkIfExist = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    A hash set of seen values turns this into one pass: for each x, look for 2x and for x / 2.

  2. Hint 2

    Only check x / 2 when x is even, or you will match a value that is not actually present.

  3. 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

  1. For each x, return true if 2x is in the set, or x is even and x / 2 is in the set.
  2. Add x to 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 / 2 for odd x in 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 False

Java

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