Given a sorted and rotated array , find if there is a pair with a given sum | C ++ 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 . ; Find the pivot element ; l is now index of smallest element ; r is now index of largest element ; Keep moving either l or r till they meet ; If we find a pair with sum x , we return true ; If current pair sum is less , move to the higher sum ; Move to the lower sum side ; Driver program to test above function
#include <iostream> NEW_LINE using namespace std ; bool pairInSortedRotated ( int arr [ ] , int n , int x ) { int i ; for ( i = 0 ; i < n - 1 ; i ++ ) if ( arr [ i ] > arr [ i + 1 ] ) break ; int l = ( i + 1 ) % n ; int r = i ; while ( l != r ) { if ( arr [ l ] + arr [ r ] == x ) return true ; if ( arr [ l ] + arr [ r ] < x ) l = ( l + 1 ) % n ; else r = ( n + r - 1 ) % n ; } return false ; } int main ( ) { int arr [ ] = { 11 , 15 , 6 , 8 , 9 , 10 } ; int sum = 16 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; if ( pairInSortedRotated ( arr , n , sum ) ) cout << " Array ▁ has ▁ two ▁ elements ▁ with ▁ sum ▁ 16" ; else cout << " Array ▁ doesn ' t ▁ have ▁ two ▁ elements ▁ with ▁ sum ▁ 16 ▁ " ; return 0 ; }