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.
``````

METHOD 1

``````/**
* Question   : Find pair in a sorted rotated array
* Complexity : Time: O(n) ; Space: O(1)
* Time       : 2020/06/11
* Author     : Max
*/
public class PairsInSortedRotated {
static void findPair(int[] arr, int target) {
if (arr.length == 0) {
return;
}

int n = arr.length;

int pivot = n - 1;
for (int i = 0; i < n - 1; i++) {
if (arr[i] > arr[i + 1]) {
pivot = i;
break;
}
}

int l = (pivot + 1) % n;
int h = pivot;

while (l != h) {
int sum = arr[l] + arr[h];
if (sum == target) {
System.out.printf("(%s, %s) ", arr[l], arr[h]);
if (l == (h - 1 + n) % n) {
break;
}
h = (h - 1 + n) % n;
l = (l + 1) % n;
} else if (sum > target) {
h = (h - 1 + n) % n;
} else {
l = (l + 1) % n;
}
}
}

public static void main(String[] args) {
int arr[] = {11, 15, 6, 7, 9, 10};
int target = 16;
findPair(arr, target);
}
}
``````