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]
Problem Statement
Given an array of integers arr, we need to check if there exist two indices i and j such that:
i != j
0 <= i, j < arr.length
arr[i] == 2 * arr[j]
In other words, we need to find if there are any two distinct indices in the array such that the value at one index is exactly twice the value
at the other index. The output of the problem should be a boolean value indicating whether such a pair exists or not.
Examples
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.
Clarifying Questions
Can the array contain negative integers?
Can the array contain non-integer values, such as floats or strings?
Is the array sorted in any particular order?
Can the array contain duplicates?
Is there any limit to the size of the array?
What should be the output if the array is empty or contains only one element?
Solutions
There are several different approaches to solving this problem, here are a few:
Approach 1: Brute Force
The simplest approach would be to compare every pair of elements in the array and check if any two of them satisfy the given condition. This would
take O(n^2) time complexity.
Algorithm:
Traverse the array and compare every pair of elements (nested loop).
If a pair is found that satisfies the given condition, return True.
If the loop completes without finding any such pair, return False.
public bool CheckIfDoubleExists(int[] arr)
{
// Traverse the array and compare every pair of elements (nested loop).
for (int i = 0; i < arr.Length; i++)
{
for (int j = 0; j < arr.Length; j++)
{
// Skip the current pair if both indices are the same.
if (i == j)
continue;
// If a pair is found that satisfies the given condition, return True.
if (arr[i] == 2 * arr[j])
return true;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
def check_if_double_exists(arr):
# Traverse the array and compare every pair of elements (nested loop).
for i in range(len(arr)):
for j in range(len(arr)):
# Skip the current pair if both indices are the same.
if i == j:
continue
# If a pair is found that satisfies the given condition, return True.
if arr[i] == 2 * arr[j]:
return True
# If the loop completes without finding any such pair, return False.
return False
public boolean checkIfDoubleExists(int[] arr) {
// Traverse the array and compare every pair of elements (nested loop).
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
// Skip the current pair if both indices are the same.
if (i == j)
continue;
// If a pair is found that satisfies the given condition, return True.
if (arr[i] == 2 * arr[j])
return true;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
bool checkIfDoubleExists(vector<int>& arr) {
// Traverse the array and compare every pair of elements (nested loop).
for (int i = 0; i < arr.size(); i++) {
for (int j = 0; j < arr.size(); j++) {
// Skip the current pair if both indices are the same.
if (i == j)
continue;
// If a pair is found that satisfies the given condition, return True.
if (arr[i] == 2 * arr[j])
return true;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
Time Complexity: The Brute force approach involves checking every possible pair of elements in the input array, so the time
complexity is O(N^2), where N is the length of the input array.
Space Complexity: The Brute force approach requires only a constant amount of extra space to store the loop variables, so the
space complexity is O(1).
Approach 2: Sorting
We can sort the array in ascending or descending order and then traverse the array from left to right, checking if the current element is twice
the previous element. This approach takes O(nlogn) time complexity due to the sorting step.
Algorithm:
Sort the array in ascending or descending order.
Traverse the array and check if the current element is twice the previous element.
If a pair is found that satisfies the given condition, return True.
If the loop completes without finding any such pair, return False.
public bool CheckIfDoubleExists(int[] arr)
{
// Sort the input array in ascending order.
Array.Sort(arr);
// Traverse the sorted array and for each element, use binary search to check if its double is present.
for (int i = 0; i < arr.Length; i++)
{
// Use binary search to check if arr[i] * 2 is present in the array.
int low = i + 1, high = arr.Length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (arr[mid] == arr[i] * 2)
return true;
else if (arr[mid] < arr[i] * 2)
low = mid + 1;
else
high = mid - 1;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
def check_if_double_exists(arr):
# Sort the input array in ascending order.
arr.sort()
# Traverse the sorted array and for each element, use binary search to check if its double is present.
for i in range(len(arr)):
# Use binary search to check if arr[i] * 2 is present in the array.
low, high = i + 1, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == arr[i] * 2:
return True
elif arr[mid] < arr[i] * 2:
low = mid + 1
else:
high = mid - 1
# If the loop completes without finding any such pair, return False.
return False
public boolean checkIfDoubleExists(int[] arr) {
// Sort the input array in ascending order.
Arrays.sort(arr);
// Traverse the sorted array and for each element, use binary search to check if its double is present.
for (int i = 0; i < arr.length; i++) {
// Use binary search to check if arr[i] * 2 is present in the array.
int low = i + 1, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == arr[i] * 2)
return true;
else if (arr[mid] < arr[i] * 2)
low = mid + 1;
else
high = mid - 1;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
bool checkIfDoubleExists(vector<int>& arr) {
// Sort the input array in ascending order.
sort(arr.begin(), arr.end());
// Traverse the sorted array and for each element, use binary search to check if its double is present.
for (int i = 0; i < arr.size(); i++) {
// Use binary search to check if arr[i] * 2 is present in the array.
int low = i + 1, high = arr.size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == arr[i] *
return true;
else if (arr[mid] < arr[i] * 2)
low = mid + 1;
else
high = mid - 1;
}
}
// If the loop completes without finding any such pair, return False.
return false;
}
Time Complexity:
The time complexity of the Sorting approach is O(N log N) due to the use of sorting and binary search.
Sorting an array of length N takes O(N log N) time using efficient algorithms such as merge sort or quicksort. After sorting, we perform binary
search on each element, which takes O(log N) time.
Therefore, the overall time complexity is O(N log N).
Space Complexity:
The space complexity of the Sorting approach is O(1) as we do not use any extra space beside a few loop variables.
The space required for sorting the input array in place depends on the sorting algorithm used, but typically it is O(log N) for the stack space
used by the recursion in merge sort or quicksort.
However, as we are not using any extra arrays to store the sorted elements, the overall space complexity remains O(1).
Approach 3: Hashing
We can use a hash table or a dictionary to keep track of the values in the array as we traverse it. For each element, we can check if its double
exists in the hash table. If it does, we have found the required pair. This approach takes O(n) time complexity.
Algorithm:
Initialize an empty hash table or dictionary.
Traverse the array and for each element:
Check if its double exists in the hash table.
If it does, return True.
If it doesn't, add the current element to the hash table.
If the loop completes without finding any such pair, return False.
public bool CheckIfDoubleExists(int[] arr) {
HashSet<int> seen = new HashSet<int>(); // initialize a hash set to keep track of numbers already seen
foreach (int num in arr) { // loop through each number in the array
// Check if the double or half of the current number is already seen
if (seen.Contains(num * 2) || (num % 2 == 0 && seen.Contains(num / 2))) {
return true; // if the double or half is already seen, return true
}
seen.Add(num); // add the current number to the set
}
return false; // if no such pair is found, return false
}
def checkIfDoubleExists(arr: List[int]) -> bool:
seen = set()
for num in arr:
# Check if the double or half of the current number is already seen
if num * 2 in seen or (num % 2 == 0 and num // 2 in seen):
return True
seen.add(num)
return False
public boolean checkIfDoubleExists(int[] arr) {
Set<Integer> seen = new HashSet<Integer>();
for (int num : arr) {
// Check if the double or half of the current number is already seen
if (seen.contains(num * 2) || (num % 2 == 0 && seen.contains(num / 2))) {
return true;
}
seen.add(num);
}
return false;
}
bool checkIfDoubleExists(vector<int>& arr) {
unordered_set<int> seen;
for (int num : arr) {
// Check if the double or half of the current number is already seen
if (seen.count(num * 2) || (num % 2 == 0 && seen.count(num / 2))) {
return true;
}
seen.insert(num);
}
return false;
}
Time Complexity:
The time complexity of the Hashing approach is O(N), where N is the length of the input array. We traverse the input array only once, and each
hash set operation takes O(1) time on average. Therefore, the overall time complexity is linear in the size of the input.
Space Complexity:
The space complexity of the Hashing approach is also O(N) because we use a hash set to store the numbers seen so far. In the worst case, all the
elements in the input array are unique, and we need to store all of them in the hash set. Therefore, the overall space complexity is linear in the
size of the input.
However, in practice, the space complexity is likely to be much smaller than O(N) because the hash set only needs to store the unique elements in
the input array.
The Brute force approach is simple and easy to understand, but it can be quite inefficient for large arrays due to its quadratic time complexity.
It may be a reasonable choice for small arrays, but for larger arrays, it is better to use other approaches such as Sorting, Hashing, or Two
pointers, which have better time complexities.
There may be other approaches to solving this problem as well, but these are a few common ones.
