# Find if there is a pair with a given sum in the rotated sorted Array

Given an array **arr[]** of distinct elements size **N** that is sorted and then around an unknown point, the task is to check if the array has a pair with a given sum **X**.

**Examples :**

Input:arr[] = {11, 15, 6, 8, 9, 10}, X = 16Output:trueExplanation:There is a pair (6, 10) with sum 16

Input:arr[] = {11, 15, 26, 38, 9, 10}, X = 35Output:trueExplanation:There is a pair (26, 9) with sum 35

**Approach:** The idea is:

First find the largest element in an array which is the pivot point also and the element just after the largest is the smallest element. Once we have the indices of the largest and the smallest elements, we use a similar

meet-in-middle algorithm(as discussed here in method 1) to find if there is a pair.The only thing new here is indices are incremented and decremented in a rotational manner using modular arithmetic.

`// Java program to find a pair with a given`

`// sum in a sorted and rotated array`

**class**`PairInSortedRotated {`

`// This function returns true if arr[0..n-1]`

`// has a pair with sum equals to x.`

**static****boolean**`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**;

`// l is now index of smallest element`

**int**`l = (i + 1) % n;`

`// r is now index of largest element`

**int**`r = i;`

`// 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;`

`// Move to the lower sum side`

**else**

`r = (n + r - 1) % n;`

`}`

**return****false**;

`}`

`/* Driver program to test above function */`

**public****static****void**`main(String[] args)`

`{`

**int**`arr[] = { 11, 15, 6, 8, 9, 10`

`};`

**int**`X = 16;`

**int**`N = arr.length;`

**if**`(pairInSortedRotated(arr, N, X))`

`System.out.print("true");`

**else**

`System.out.print("false");`

`}`

`}`

**Output**

`true`

**Time Complexity: **O(N). The step to find the pivot can be optimized to O(Logn) using the Binary Search approach discussed here.**Auxiliary Space: **O(1).