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:

1Input: arr = [10,2,5,3]
2Output: true
3Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

1Input: arr = [3,1,7,11]
2Output: false
3Explanation: There is no i and j that satisfy the conditions.

Constraints:

  • 2 <= arr.length <= 500
  • -10^3 <= arr[i] <= 10^3

Solution

Using Brute Force Approach

The simplest brute force approach would involve iterating arr two times while checking each number, check for its double exists in the nested iteration while making sure that index is not the same one. This approach would give us time complexity of O(n^2).

 1class Solution {
 2    public boolean checkIfExists (int[] arr) {
 3        for (int i = 0; i < arr.length; i++) {
 4            for (int j = 0; j < arr.length; j++) {
 5                if (arr[i] == 2 * arr[j] && i != j) {
 6                    return true;
 7                }
 8            }
 9        }
10        return false;
11    }
12}

Another alternative is to use sorting and searching. If we sort the array into ascending order, for each number in arr, we will have to search for a number which is double of current number. We could use binary search once the array is sorted. This binary search will be slightly different than normal binary search because in this one, we will have to make sure that we are not returning true when the same index position is found.

 1class Solution {
 2    private int binarySearch(int[] arr, int target) {
 3        int left = 0, right = arr.length - 1;
 4        int middle;
 5        while (left <= right) {
 6            middle = (right + left) / 2;
 7            if (arr[middle] > target)
 8                right = middle - 1;
 9            else if (arr[middle] < target)
10                left = middle + 1;
11            else
12                return middle;
13        }
14        return -1;
15    }
16
17    public boolean checkIfExists (int[] arr) {
18        Arrays.sort(arr);
19        for (int i = 0; i < arr.length; i++) {
20            if (binarySearch(arr, arr[i] * 2) != -1) {
21                return true;
22            }
23        }
24        return false;
25    }
26}

Although this solution works in most scenarios because we are checking for a different number (i.e. number n and 2 * n will be different), there is scenario where both are equal. If n = 0, then its double is also same, so in this case, this simple binary search will find the same index and return true which is incorrect solution.

We can improvise this binary search to always neglect the current index or when checking the results of this binary search, we have to make sure it’s not the same index. The checkIfExists method gets modified like below.

 1    public boolean checkIfExist (int[] arr) {
 2        Arrays.sort(arr);
 3        for (int i = 0; i < arr.length; i++) {
 4            int index = binarySearch(arr, arr[i] * 2);
 5            if (index != -1 && index != i) {
 6                return true;
 7            }
 8        }
 9        return false;
10    }

Another alternative is to omit the current index always and in fact, omit all the indices before current index as well because we have already iterated through those indices.

 1class Solution {
 2    private int binarySearch(int[] arr, int target, int i) {
 3        int left = i + 1, right = arr.length - 1;
 4        while (left <= right) {
 5            int middle = (right - left) / 2 + left;
 6            if (arr[middle] > target) {
 7                right = middle - 1;
 8            } else if (arr[middle] < target) {
 9                left = middle + 1;
10            } else {
11                return middle;
12            }
13        }
14        return -1;
15    }
16
17    public boolean checkIfExists(int[] arr) {
18
19        Arrays.sort(arr);
20        for (int i = 0; i < arr.length; i++) {
21            if (binarySearch(arr, arr[i] * 2, i) != -1) {
22                return true;
23            }
24        }
25        return false;
26    }
27}
  • Time Complexity: O(n log n)
  • Space Complexity: O(1)

Using Hashing

Third option is to use hashing approach. In this case we are always looking for a number in relation to existing number, so we can store currently seen numbers into HashSet or HashMap and while passing through each element of the array, we check if it’s half or double exists in the HashSet. To find the half, we have to make sure current number is even before finding its half.

 1class Solution {
 2    public boolean checkIfExist(int[] arr) {
 3        Set<Integer> set = new java.util.HashSet<>();
 4        for (int i = 0; i < arr.length; i++) {
 5            if (set.contains(arr[i] * 2) || (arr[i] % 2 == 0 && set.contains(arr[i] / 2))) {
 6                return true;
 7            }
 8            set.add(arr[i]);
 9        }
10        return false;
11    }
12}