 # Check If N and Its Double Exist

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

1. Given an array of integers `arr`, we need to check if there exist two indices `i` and `j` such that:

2. `i != j`
3. `0 <= i, j < arr.length`
4. `arr[i] == 2 * arr[j]`
5. 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

1. Can the array contain negative integers?
2. Can the array contain non-integer values, such as floats or strings?
3. Is the array sorted in any particular order?
4. Can the array contain duplicates?
5. Is there any limit to the size of the array?
6. 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:

1. Traverse the array and compare every pair of elements (nested loop).
2. If a pair is found that satisfies the given condition, return True.
3. If the loop completes without finding any such pair, 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.

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.

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.

Share: 