Open In App

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

Last Updated : 19 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given an array arr[] of distinct elements size N that is sorted and then rotated 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 = 16
Output: true
Explanation: There is a pair (6, 10) with sum 16

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

Input: arr[] = {11, 15, 26, 38, 9, 10}, X = 45
Output: false
Explanation: There is no pair with sum 45.

We have discussed an O(n) solution for a sorted array (See steps 2, 3, and 4 of Method 1) in this article. We can extend this solution for the rotated arrays as well. 

Practice: Pair with given sum in a sorted array

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.

Illustration:

Let us take an example arr[]={11, 15, 6, 8, 9, 10}, sum=16.
pivot = 1,  

l = 2, r = 1:
        => arr[2] + arr[1] = 6 + 15 = 21 which is > 16 
        => So decrement r circularly. r = ( 6 + 1 – 1) % 6, r = 0

l = 2, r = 0:
        => arr[2] + arr[0] = 17 which is > 16. 
        => So decrement r circularly. r = (6 + 0 – 1) % 6, r = 5

l = 2, r = 5:
        => arr[2] + arr[5] = 16 which is equal to 16. 
        => Hence return true

Hence there exists such a pair.

Follow the steps mentioned below to implement the idea:

  • We will run a for loop from 0 to N-1, to find out the pivot point. 
  • Set the left pointer(l) to the smallest value and the right pointer(r) to the highest value.
  • To restrict the circular movement within the array we will apply the modulo operation by the size of the array.
  • While l ! = r, we shall keep checking if arr[l] + arr[r] = sum.
    • If arr[l] + arr[r] is greater than X, update r = (N+r-1) % N.
    • If arr[l] + arr[r] is less than X, update l = (l+1) % N.
    • If arr[l] + arr[r] is equal to the value X, then return true.
  • If no such pair is found after the iteration is complete, return false.

Below is the implementation of the above approach. 

C++
// C++ code to implement the approach

#include <bits/stdc++.h>
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;

    // 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 code
int main()
{
    int arr[] = { 11, 15, 6, 8, 9, 10 };
    int X = 16;
    int N = sizeof(arr) / sizeof(arr[0]);

    // Function call
    if (pairInSortedRotated(arr, N, X))
        cout << "true";
    else
        cout << "false";

    return 0;
}
Java
// Java program to find a pair with a given
// sum in a sorted and rotated array
import java.io.*;

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");
    }
}
/*This code is contributed by Prakriti Gupta*/
Python3
# Python3 program to find a
# pair with a given sum in
# a sorted and rotated array


# This function returns True
# if arr[0..n-1] has a pair
# with sum equals to x.
def pairInSortedRotated(arr, n, x):

    # Find the pivot element
    for i in range(0, n - 1):
        if (arr[i] > arr[i + 1]):
            break

    # l is now index of smallest element
    l = (i + 1) % n
    # r is now index of largest element
    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
        else:

            # Move to the lower sum side
            r = (n + r - 1) % n

    return False


# Driver program to test above function
arr = [11, 15, 6, 8, 9, 10]
X = 16
N = len(arr)

if (pairInSortedRotated(arr, N, X)):
    print("true")
else:
    print("false")


# This article contributed by saloni1297
C#
// C# program to find a pair with a given
// sum in a sorted and rotated array
using System;

class PairInSortedRotated {
    // This function returns true if arr[0..n-1]
    // has a pair with sum equals to x.
    static 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;

        // 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 Code
    public static void Main()
    {
        int[] arr = { 11, 15, 6, 8, 9, 10 };
        int X = 16;
        int N = arr.Length;

        if (pairInSortedRotated(arr, N, X))
            Console.WriteLine("true");
        else
            Console.WriteLine("false");
    }
}

// This code is contributed by vt_m.
Javascript
<script>

// Javascript program to find a 
// pair with a given sum in a 
// sorted and rotated array
    
// This function returns true if arr[0..n-1] 
// has a pair with sum equals to x.
function pairInSortedRotated(arr, n, x)
{
    
    // Find the pivot element
    let i;
    for(i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
            break;
            
    // l is now index of                                          
    // smallest element          
    let l = (i + 1) % n; 
    
    // r is now index of largest 
    // element                   
    let 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 code
let arr = [ 11, 15, 6, 8, 9, 10 ];
let X = 16;
let N = arr.length;

if (pairInSortedRotated(arr, N, X))
    document.write("true");
else
    document.write("false");

// This code is contributed by avanitrachhadiya2155
    
</script>
PHP
<?php
// PHP program to find a pair
// with a given sum in a
// sorted and rotated array

// This function returns true
// if arr[0..n-1] has a pair 
// with sum equals to x.

function pairInSortedRotated($arr, $n, $x)
{
    // Find the pivot element
    $i;
    for ($i = 0; $i < $n - 1; $i++)
        if ($arr[$i] > $arr[$i + 1])
            break;
        
    // l is now index of 
    // smallest element
    $l = ($i + 1) % $n; 
    
    // r is now index of
    // largest element
    $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 Code
$arr = array(11, 15, 6, 8, 9, 10);
$X = 16;
$N = sizeof($arr);

if (pairInSortedRotated($arr, $N, $X))
    echo "true";
else
    echo "false";

// This code is contributed by aj_36
?>

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

Exercise: 
1) Extend the above solution to work for arrays with duplicates allowed.

Approach#2: Using two pointers and binary search

The approach finds the pivot element in the rotated sorted array and then uses two pointers to check if there is a pair with a given sum. The pointers move in a circular way using the modulo operator.

Algorithm

1. Find the pivot element in the rotated sorted array. If the pivot element is greater than the first element of the array, then the pivot lies in the second half of the array; otherwise, it lies in the first half of the array.
2. After finding the pivot element, initialize two pointers left and right at the start and end of the array, respectively.
3. Loop through the array and check if the sum of the elements at the left and right pointers is equal to the given sum. If it is, then return true.
4. If the sum is less than the given sum, increment the left pointer, else decrement the right pointer.
5. If the loop completes and no pair is found, return false.

C++
#include <iostream>
using namespace std;

// Function to find a pair with a given sum in a sorted and
// rotated array
bool findPair(int arr[], int n, int x)
{
    // find pivot element
    int pivot = 0;
    for (int i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            pivot = i + 1;
            break;
        }
    }
    // set left and right pointers
    int left = pivot;
    int right = pivot - 1;
    // loop until left and right pointers meet
    while (left != right) {
        // if sum of elements at left and right pointers is
        // equal to x, return true
        if (arr[left] + arr[right] == x) {
            return true;
        }
        // if sum of elements at left and right pointers is
        // less than x, move left pointer to the next
        // element
        else if (arr[left] + arr[right] < x) {
            left = (left + 1) % n;
        }
        // if sum of elements at left and right pointers is
        // greater than x, move right pointer to the
        // previous element
        else {
            right = (right - 1 + n) % n;
        }
    }
    // return false if pair not found
    return false;
}

int main()
{
    // initialize array and variables
    int arr[] = { 11, 15, 6, 8, 9, 10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 16;
    // call function and print result
    cout << boolalpha << findPair(arr, n, x);
    return 0;
}
Java
public class FindPairInRotatedArray {
    public static boolean findPair(int[] arr, int x) {
        int n = arr.length;
        // find pivot element
        int pivot = 0;
        for (int i = 0; i < n-1; i++) {
            if (arr[i] > arr[i+1]) {
                pivot = i+1;
                break;
            }
        }
        int left = pivot;
        int right = pivot-1;
        while (left != right) {
            if (arr[left] + arr[right] == x) {
                return true;
            }
            else if (arr[left] + arr[right] < x) {
                left = (left+1) % n;
            }
            else {
                right = (right-1+n) % n;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] arr = {11, 15, 6, 8, 9, 10};
        int x = 16;
        System.out.println(findPair(arr, x));
    }
}
Python3
def find_pair(arr, x):
    n = len(arr)
    # find pivot element
    pivot = 0
    for i in range(n-1):
        if arr[i] > arr[i+1]:
            pivot = i+1
            break
    left = pivot
    right = pivot-1
    while left != right:
        if arr[left] + arr[right] == x:
            return True
        elif arr[left] + arr[right] < x:
            left = (left+1) % n
        else:
            right = (right-1+n) % n
    return False

arr = [11, 15, 6, 8, 9, 10]
x = 16
print(find_pair(arr, x))  
C#
using System;

public class FindPairInRotatedArray {
  public static bool FindPair(int[] arr, int x) {
    int n = arr.Length;
    
    // find pivot element
    int pivot = 0;
    for (int i = 0; i < n-1; i++) {
      if (arr[i] > arr[i+1]) {
        pivot = i+1;
        break;
      }
    }
    int left = pivot;
    int right = pivot-1;
    while (left != right) {
      if (arr[left] + arr[right] == x) {
        return true;
      }
      else if (arr[left] + arr[right] < x) {
        left = (left+1) % n;
      }
      else {
        right = (right-1+n) % n;
      }
    }
    return false;
  }
  public static void Main(string[] args) {
    int[] arr = {11, 15, 6, 8, 9, 10};
    int x = 16;
    Console.WriteLine(FindPair(arr, x));
  }
}
Javascript
function findPair(arr, x) {
    const n = arr.length;
    // find pivot element
    let pivot = 0;
    for (let i = 0; i < n - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            pivot = i + 1;
            break;
        }
    }
    let left = pivot;
    let right = pivot - 1;
    while (left !== right) {
        if (arr[left] + arr[right] === x) {
            return true;
        } else if (arr[left] + arr[right] < x) {
            left = (left + 1) % n;
        } else {
            right = (right - 1 + n) % n;
        }
    }
    return false;
}

const arr = [11, 15, 6, 8, 9, 10];
const x = 16;
console.log(findPair(arr, x));

Output
True

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

Space Complexity: O(1).
 



Previous Article
Next Article

Similar Reads

C++ Program for Given a sorted and rotated array, find if there is a pair with a given sum
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
6 min read
C Program for Given a sorted and rotated array, find if there is a pair with a given sum
Write a C program for a given array arr[] of distinct elements size N that is sorted and then rotated 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
7 min read
Java Program for Given a sorted and rotated array, find if there is a pair with a given sum
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
6 min read
Circularly Sorted Array (Sorted and Rotated Array)
Circularly sorted arrays are arrays that are sorted in ascending or descending order and then rotated by a number of steps. Let us take an example to know more about circularly sorted arrays: Consider an array: arr[] = {23, 34, 45, 12, 17, 19}The elements here, {12, 17, 19, 23, 34, 45} are sorted 'In-order' but they are rotated to the left by 3 tim
7 min read
Count of Pairs with given sum in 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 count the number of pairs in the array having a given sum X. Examples: Input: arr[] = {11, 15, 26, 38, 9, 10}, X = 35Output: 1Explanation: There is a pair (26, 9) with sum 35 Input: arr[] = {11, 15, 6, 7, 9, 10}, X = 16Output: 2 Approach
13 min read
Find the Rotation Count in Rotated Sorted array
Given an array arr[] of size N having distinct numbers sorted in increasing order and the array has been right rotated (i.e, the last element will be cyclically shifted to the starting position of the array) k number of times, the task is to find the value of k. Examples: Input: arr[] = {15, 18, 2, 3, 6, 12}Output: 2Explanation: Initial array must
15+ min read
Find the Minimum element in a Sorted and Rotated Array
Given a sorted array arr[] (may be distinct or may contain duplicates) of size N that is rotated at some unknown point, the task is to find the minimum element in it. Examples: Input: arr[] = {5, 6, 1, 2, 3, 4}Output: 1Explanation: 1 is the minimum element present in the array. Input: arr[] = {1, 2, 3, 4}Output: 1 Input: arr[] = {2, 1}Output: 1 Rec
10 min read
Count elements less than or equal to a given value in a sorted rotated array
Given a sorted array of n distinct integers rotated at some point. Given a value x. The problem is to count all the elements in the array which are less than or equal to x. Examples: Input : arr[] = {4, 5, 8, 1, 3}, x = 6 Output : 4 Input : arr[] = {6, 10, 12, 15, 2, 4, 5}, x = 14 Output : 6 Naive Approach: One by one traverse all the elements of t
15 min read
Given a sorted array and a number x, find the pair in array whose sum is closest to x
Given a sorted array and a number x, find a pair in an array whose sum is closest to x. Examples: Input: arr[] = {10, 22, 28, 29, 30, 40}, x = 54 Output: 22 and 30 Input: arr[] = {1, 3, 4, 7, 10}, x = 15 Output: 4 and 10Naive Approach:- A simple solution is to consider every pair and keep track of the closest pair (the absolute difference between p
15+ min read
Check if two sorted arrays can be merged to form a sorted array with no adjacent pair from the same array
Given two sorted arrays A[] and B[] of size N, the task is to check if it is possible to merge two given sorted arrays into a new sorted array such that no two consecutive elements are from the same array. Examples: Input: A[] = {3, 5, 8}, B[] = {2, 4, 6}Output: Yes Explanation: Merged array = {B[0], A[0], B[1], A[1], B[2], A[2]} Since the resultan
15+ min read
Article Tags :
Practice Tags :
three90RightbarBannerImg