Given a sorted and rotated array, find if there is a pair with a given sum - GeeksforGeeks
Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum 'x'. It may be assumed that all elements in array are distinct.
The idea is to first find the maximum element in array which is the pivot point also and the element just before maximum is the minimum element. Once we have indexes maximum and minimum elements, we use similar meet in middle algorithm (as discussed here in method 1) to find if there is a pair. The only thing new here is indexes are incremented and decremented in rotational manner using modular arithmetic.
Given an array that is sorted and then rotated around an unknown point. Find if array has a pair with given sum 'x'. It may be assumed that all elements in array are distinct.
The idea is to first find the maximum element in array which is the pivot point also and the element just before maximum is the minimum element. Once we have indexes maximum and minimum elements, we use similar meet in middle algorithm (as discussed here in method 1) to find if there is a pair. The only thing new here is indexes are incremented and decremented in rotational manner using modular arithmetic.
bool
pairInSortedRotated(
int
arr[],
int
n,
int
x)
{
// Find the pivot element
int
i;
for
(i=0; i<n-1; i++)
if
(arr[i] > arr[i+1])
break
;
int
l = (i+1)%n;
// l is now index of minimum element
int
r = i;
// r is now index of maximum element
// Keep moving either l or r till they meet
while
(l != r)
{
// If we find a pair with sum x, we return true
if
(arr[l] + arr[r] == x)
return
true
;
// If current pair sum is less, move to the higher sum
if
(arr[l] + arr[r] < x)
l = (l + 1)%n;
else
// Move to the lower sum side
r = (n + r - 1)%n;
}
return
false
;
}
1) Extend the above solution to work for arrays with duplicates allowed.
2) Extend the above solution to find all pairs.
Read full article from Given a sorted and rotated array, find if there is a pair with a given sum - GeeksforGeeks