×

# Given a sorted and rotated array, find if there is a pair with a given sum

Given a sorted and rotated array, find if there is a pair with a given sum using C++ programs?
Submitted by Vikneshwar GK, on February 20, 2022

Consider an integer array of size n that is sorted in ascending order and then rotated using a pivot value that is unknown. Given an integer x, find if there exists a pair in the array such that the sum of elements of the pair is the integer x.

## Example

```Input:
array[]= {5, 1, 2, 3, 4}
element = 5

Output:
Pair is present

Explanation:
(2, 3) sum is 5

Input:
array[]= {50, 10, 20, 30, 40}
element = 25

Output:
Pair is not present
```

Solution 1: Find pivot value and search

This is a simple approach that involves finding the pivot element in the given array. The pivot element is the one that has the largest value and the next element after it is the smallest element in the array. After finding it we can use two pointers to point those elements and find the pair by incrementing and decrementing the pointers in a rotational manner using modular arithmetic.

## C++ Implementation

```#include <iostream>
using namespace std;

// Function to find pair that equals sum x
bool findPair(int array[], int length, int x)
{
// Find the pivot element
int i;
for (i = 0; i < length - 1; i++)
if (array[i] > array[i + 1])
break;

//min element
int left = (i + 1) % length;
//max element
int right = i;

while (left != right) {
if (array[left] + array[right] == x)
return true;

// increment or decrement pointers
if (array[left] + array[right] < x)
left = (left + 1) % length;
else
right = (length + right - 1) % length;
}
return false;
}

// Main function
int main()
{
int array[100], N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the element to find pair: ";
cin >> element;

int index = findPair(array, N, element);
if (index == false) {
cout << "Pair is not present";
}
else {
cout << "Pair is present";
}

return 0;
}
```

Output:

```Enter Number of elements: 5
Enter element 1:6
Enter element 2:7
Enter element 3:1
Enter element 4:2
Enter element 5:3
Enter the element to find pair: 4
Pair is present
```

Time Complexity: O(n), where n is the length of the array.

Solution 2: Find pair count

• Find the pivot element by traversing the array. The pivot element is the one whose next element is less than itself, i.e., array[pivot]<array[pivot+1]
• Use two pointers, left and right, with the right pointer pointing the pivot element and left pointing to its next element
• Add elements at left and right
• If the sum is lesser than the input value, increment left pointer in a rotation manner
• If the sum is greater than the input value, decrement the right pointer in a rotation manner
• If the sum is equal to the input value, increment the counter and increment and decrement left and right pointer respectively in a rotational manner
• Perform the above steps until left and right pointers are not equal or left pointer not equal to right pointer-1
• Print the count

## C++ Implementation

```#include <iostream>
using namespace std;

// Function to find pair that equals sum x
#include <bits/stdc++.h>
using namespace std;

// This function returns count of number of pairs
// with sum equals to x.
int findPair(int array[], int length, int x)
{
int i;

// find the pivot element
for (i = 0; i < length - 1; i++)
if (array[i] > array[i + 1])
break;

//left pointer
int left = (i + 1) % length;

//right pointer
int right = i;

int count = 0;

//iterate until left is not equal to right
while (left != right) {
if (array[left] + array[right] == x) {
count++;

// check left is right + 1
if (left == (right - 1 + length) % length) {
return count;
}

left = (left + 1) % length;
right = (right - 1 + length) % length;
}

// increment left
else if (array[left] + array[right] < x)
left = (left + 1) % length;

// decrement right
else
right = (length + right - 1) % length;
}
return count;
}

// Main function
int main()
{
int array[100], N, element;

cout << "Enter Number of elements: ";
cin >> N;

for (int i = 0; i < N; i++) {
cout << "Enter element " << i + 1 << ":";
cin >> array[i];
}
cout << "Enter the element to find pair: ";
cin >> element;

int count = findPair(array, N, element);
if (count == 0) {
cout << "Pair is not present";
}
else {
cout << "No. of pairs present: " << count;
}

return 0;
}
```

Output:

```Enter Number of elements: 6
Enter element 1:11
Enter element 2:15
Enter element 3:6
Enter element 4:7
Enter element 5:9
Enter element 6:10
Enter the element to find pair: 16
No. of pairs present: 2
```

Time Complexity: O(n), where n is the length of the array.