Home » Data Structure » Array Data Structure

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.