Description#
Given an array arr of integers, check if there exist two indices i and j such that :
i != j0 <= i, j < arr.lengtharr[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#
1
2
3
4
| class Solution:
def checkIfExist(self, arr: List[int]) -> bool:
m = {v: i for i, v in enumerate(arr)}
return any(v << 1 in m and m[v << 1] != i for i, v in enumerate(arr))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean checkIfExist(int[] arr) {
Map<Integer, Integer> m = new HashMap<>();
int n = arr.length;
for (int i = 0; i < n; ++i) {
m.put(arr[i], i);
}
for (int i = 0; i < n; ++i) {
if (m.containsKey(arr[i] << 1) && m.get(arr[i] << 1) != i) {
return true;
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
bool checkIfExist(vector<int>& arr) {
unordered_map<int, int> m;
int n = arr.size();
for (int i = 0; i < n; ++i) m[arr[i]] = i;
for (int i = 0; i < n; ++i)
if (m.count(arr[i] * 2) && m[arr[i] * 2] != i)
return true;
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
| func checkIfExist(arr []int) bool {
m := make(map[int]int)
for i, v := range arr {
m[v] = i
}
for i, v := range arr {
if j, ok := m[v*2]; ok && j != i {
return true
}
}
return false
}
|
1
2
3
4
5
6
7
8
9
10
| function checkIfExist(arr: number[]): boolean {
const s = new Set();
for (const v of arr) {
if (s.has(v << 1) || s.has(v / 2)) {
return true;
}
s.add(v);
}
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| use std::collections::HashMap;
impl Solution {
pub fn check_if_exist(arr: Vec<i32>) -> bool {
let mut map = HashMap::new();
for (i, v) in arr.iter().enumerate() {
map.insert(v, i);
}
for (i, v) in arr.iter().enumerate() {
if map.contains_key(&(v * 2)) && map[&(v * 2)] != i {
return true;
}
}
false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| /**
* @param {number[]} arr
* @return {boolean}
*/
var checkIfExist = function (arr) {
const s = new Set();
for (const v of arr) {
if (s.has(v << 1) || s.has(v / 2)) {
return true;
}
s.add(v);
}
return false;
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
/**
* @param Integer[] $arr
* @return Boolean
*/
function checkIfExist($arr) {
for ($i = 0; $i < count($arr); $i++) {
$hashtable[$arr[$i] * 2] = $i;
}
for ($i = 0; $i < count($arr); $i++) {
if (isset($hashtable[$arr[$i]]) && $hashtable[$arr[$i]] != $i) {
return true;
}
}
return false;
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
| class Solution:
def checkIfExist(self, arr: List[int]) -> bool:
s = set()
for v in arr:
if v * 2 in s or (v % 2 == 0 and v // 2 in s):
return True
s.add(v)
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 v : arr) {
if (s.contains(v * 2) || (v % 2 == 0 && s.contains(v / 2))) {
return true;
}
s.add(v);
}
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& v : arr) {
if (s.count(v * 2) || (v % 2 == 0 && s.count(v / 2))) {
return true;
}
s.insert(v);
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
| func checkIfExist(arr []int) bool {
s := map[int]bool{}
for _, v := range arr {
if s[v*2] || (v%2 == 0 && s[v/2]) {
return true
}
s[v] = true
}
return false
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| function checkIfExist(arr: number[]): boolean {
let cnt = 0;
for (const v of arr) {
if (v == 0) {
++cnt;
if (cnt > 1) {
return true;
}
}
}
const n = arr.length;
arr.sort((a, b) => a - b);
for (const v of arr) {
if (v != 0) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (arr[mid] >= v * 2) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && arr[left] == v * 2) {
return true;
}
}
}
return false;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| use std::cmp::Ordering;
impl Solution {
pub fn check_if_exist(mut arr: Vec<i32>) -> bool {
arr.sort();
let n = arr.len();
for i in 0..n {
let target = arr[i] * 2;
let mut left = 0;
let mut right = n;
while left < right {
let mid = left + (right - left) / 2;
match arr[mid].cmp(&target) {
Ordering::Less => {
left = mid + 1;
}
Ordering::Greater => {
right = mid;
}
Ordering::Equal => {
if mid == i {
break;
}
return true;
}
}
}
}
false
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| /**
* @param {number[]} arr
* @return {boolean}
*/
var checkIfExist = function (arr) {
let cnt = 0;
for (const v of arr) {
if (v == 0) {
++cnt;
if (cnt > 1) {
return true;
}
}
}
const n = arr.length;
arr.sort((a, b) => a - b);
for (const v of arr) {
if (v != 0) {
let left = 0,
right = n;
while (left < right) {
const mid = (left + right) >> 1;
if (arr[mid] >= v * 2) {
right = mid;
} else {
left = mid + 1;
}
}
if (left != n && arr[left] == v * 2) {
return true;
}
}
}
return false;
};
|
Solution 3#
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def checkIfExist(self, arr: List[int]) -> bool:
if arr.count(0) > 1:
return True
arr.sort()
n = len(arr)
for v in arr:
idx = bisect_left(arr, v * 2)
if v != 0 and idx != n and arr[idx] == v * 2:
return True
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public boolean checkIfExist(int[] arr) {
int cnt = 0;
for (int v : arr) {
if (v == 0) {
++cnt;
if (cnt > 1) {
return true;
}
}
}
Arrays.sort(arr);
for (int v : arr) {
if (v != 0) {
int idx = Arrays.binarySearch(arr, v * 2);
if (idx >= 0) {
return true;
}
}
}
return false;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
bool checkIfExist(vector<int>& arr) {
int cnt = 0;
for (int& v : arr)
if (v == 0) ++cnt;
if (cnt > 1) return true;
sort(arr.begin(), arr.end());
int n = arr.size();
for (int& v : arr) {
if (v == 0) continue;
int idx = lower_bound(arr.begin(), arr.end(), v * 2) - arr.begin();
if (idx != n && arr[idx] == v * 2) return true;
}
return false;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| func checkIfExist(arr []int) bool {
cnt := 0
for _, v := range arr {
if v == 0 {
cnt++
if cnt > 1 {
return true
}
}
}
sort.Ints(arr)
n := len(arr)
for _, v := range arr {
if v != 0 {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if arr[mid] >= v*2 {
right = mid
} else {
left = mid + 1
}
}
if right != n && arr[left] == v*2 {
return true
}
}
}
return false
}
|
