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