Given an unsorted array and a number n, find if there exists a pair of elements in the array whose difference is n.
We can use sorting and Binary Search to improve time complexity to O(nLogn). The first step is to sort the array in ascending order. Once the array is sorted, traverse the array from left to right, and for each element arr[i], binary search for arr[i] + n in arr[i+1..n-1]. If the element is found, return the pair.
Both first and second steps take O(nLogn). So overall complexity is O(nLogn).
The second step of the above algorithm can be improved to O(n). The first step remain same. The idea for second step is take two index variables i and j, initialize them as 0 and 1 respectively. Now run a linear loop. If arr[j] – arr[i] is smaller than n, we need to look for greater arr[j], so increment j. If arr[j] – arr[i] is greater than n, we need to look for greater arr[i], so increment i.
We can use sorting and Binary Search to improve time complexity to O(nLogn). The first step is to sort the array in ascending order. Once the array is sorted, traverse the array from left to right, and for each element arr[i], binary search for arr[i] + n in arr[i+1..n-1]. If the element is found, return the pair.
Both first and second steps take O(nLogn). So overall complexity is O(nLogn).
The second step of the above algorithm can be improved to O(n). The first step remain same. The idea for second step is take two index variables i and j, initialize them as 0 and 1 respectively. Now run a linear loop. If arr[j] – arr[i] is smaller than n, we need to look for greater arr[j], so increment j. If arr[j] – arr[i] is greater than n, we need to look for greater arr[i], so increment i.
// The function assumes that the array is sorted
bool
findPair(
int
arr[],
int
size,
int
n)
{
// Initialize positions of two elements
int
i = 0;
int
j = 1;
// Search for a pair
while
(i<size && j<size)
{
if
(i != j && arr[j]-arr[i] == n)
{
printf
(
"Pair Found: (%d, %d)"
, arr[i], arr[j]);
return
true
;
}
else
if
(arr[j]-arr[i] < n)
j++;
else
i++;
}
printf
(
"No such pair"
);
return
false
;
}
Hashing can also be used to solve this problem. Create an empty hash table HT. Traverse the array, use array elements as hash keys and enter them in HT. Traverse the array again look for value n + arr[i] in HT.
Read full article from Find a pair with the given difference | GeeksforGeeks