Given an array that is sorted and then rotated around an unknown point. Find if the array has a pair with a given sum ‘x’. It may be assumed that all elements in the array are distinct.
Examples :
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16 Output: true There is a pair (6, 10) with sum 16 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35 Output: true There is a pair (26, 9) with sum 35 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 45 Output: false There is no pair with sum 45.
Given an array that is sorted and then rotated around an unknown point. Find if the array has a pair with a given sum ‘x’. It may be assumed that all elements in the array are distinct.
Examples :
Input: arr[] = {11, 15, 6, 8, 9, 10}, x = 16 Output: true There is a pair (6, 10) with sum 16 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 35 Output: true There is a pair (26, 9) with sum 35 Input: arr[] = {11, 15, 26, 38, 9, 10}, x = 45 Output: false There is no pair with sum 45.
We can extend this solution for rotated array as well. The idea is to first find the largest element in array which is the pivot point also and the element just after largest is the smallest element. Once we have indexes largest and smallest elements, we use similar meet in middle algorithm to find if there is a pair. The only thing new here is indexes are incremented and decremented in rotational manner using modular arithmetic.
Following is the implementation of above idea.
// C++ program to find a pair with a given sum in a sorted and
// rotated array
#include<iostream>
using
namespace
std;
// This function returns true if arr[0..n-1] has a pair
// with sum equals to x.
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 smallest element
`` int
r = i;
// r is now index of largest 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
;
}
/* Driver program to test above function */
int
main()
{
`` int
arr[] = {11, 15, 6, 8, 9, 10};
`` int
sum = 16;
`` int
n =
sizeof
(arr)/
sizeof
(arr[0]);
`` if
(pairInSortedRotated(arr, n, sum))
`` cout <<
"Array has two elements with sum 16"
;
`` else
`` cout <<
"Array doesn't have two elements with sum 16 "
;
`` return
0;
}
Output :
Array has two elements with sum 16
The time complexity of the above solution is O(n). The step to find the pivot can be optimized to O(Logn) using the Binary Search approach discussed.