Find Pair Sum in Rotated and Sorted array

#include <bits/stdc++.h>

bool findPairSum(vector<int> arr, int target) {
    int n = arr.size();
    int low = 0;
    int high = n - 1;
    int pivot = 0;

    while (low <= high) {
        int mid = (high - low) / 2 + low;

        if (arr[mid + 1] < arr[mid]) {
            pivot = mid + 1;
            break;
        }

        if (arr[mid - 1] > arr[mid]) {
            pivot = mid;
            break;
        }

        if (arr[high] < arr[mid]) {
            low = mid + 1;
        } 
        else {
            high = mid - 1;
        }
    }

    int st = pivot;
    int end = (n + pivot - 1) % n;

    while (st != end) {
        int temp = arr[st] + arr[end];

        if (temp == target) {
            return true;
        } 
        else if (temp < target) {
            st = (st + 1) % n;
        } 
        else {
            end = (n + end - 1) % n;
        }
    }
    return false;
}

As it is rotated sorted array so i just made it unrotated sorted array that means i just sort the whole array by using inbuilt sorting system in Java. If you want you can do this sorting by using mergeSort or further better algorithm.  

Then I create two pointer start and end which indicate the first position and last position of the array and i compare the sum of this two pointer with the targetted value.  If targetted value is small then decrement the end by one else increment the start by one.  If targetted value is equal to it's sum then return true. else the loop will iterate until start is greater than or equal to end.  if it not return inside the loop it will return false as it came outside from that loop

The overall time complexity of the code is O(n log n) due to the sorting operation.

As for space complexity, the code uses only a constant amount of extra space for variables like start, end, and sum, regardless of the size of the input array. So, the space complexity is O(1), indicating constant space usage. Please upvote me.

import java.util.*;

public class Solution {

    public static boolean findPairSum(int[] arr, int target) {
        Arrays.sort(arr);
        int start = 0;
        int end = arr.length - 1;

        while (start < end) {
            int sum = arr[start] + arr[end];
            if (sum == target) {
                return true;
            } else if (sum < target) {
                start++;
            } else {
                end--;
            }
        }
        return false;
    }
}

def findPairSum(arr, target):
    dict={}
    for i,num in enumerate (arr):
        want=target-arr[i]
        if want in dict:
            return True
        
        dict[num]=1


    return False

sort(arr.begin(),arr.end());

int n=arr.size();

int s=0;

int e=n-1;

while(s<e){

if(arr[s]+arr[e]==target){

return true;

}

else if(arr[s]+arr[e]<target){

s++;

}

else{

e--;

}

}

return false;

#include <bits/stdc++.h>
using namespace std;

int findPairSum(vector<int> &arr, int target) {
  sort(arr.begin(), arr.end());
  unordered_map<int, int> mp;

  for (auto num : arr) {
    if (mp.count(target - num))
      return true;

    mp[num]++;
  }

  return false;
}

Optimized java solution:-

import java.util.* ;

import java.io.*; 

public class Solution 

{

    public static boolean findPairSum(int[] a, int sum) 

    {

        int n=a.length;

        int s=pivot(a);

        int e=(s-1+n)%n;

        while(s!=e){

            if((a[s]+a[e])==sum){

                return true;

            }else if((a[s]+a[e])<sum){

                s=(s+1)%n;

            }else{

                e=(e-1+n)%n;

            }

        }

        return false;

    }

    public static int pivot(int a[]){

        int s=0,e=a.length-1;

        if(a.length==1) return 0;

        if(a[s]<a[e]) return 0;

        while(s<=e){

            int m=s+(e-s)/2;

            if(a[m]>a[m+1]) return m+1;

            if(a[m-1]>a[m]) return m;

            if(a[s]<a[m]) {

                s=m+1;

            }else{

                e=m-1;

            }

        }

        return -1;

    }

}

// Write your code here

        for(int i = 0;i<arr.length;i++){

            for(int j = i+1;j<arr.length;j++){

                if((arr[i]+arr[j])==target)return true;

            }

        }

        return false;

def findPairSum(arr, target):
    #Write your code here
    n=len(arr)
    i=0
    while i<n-1:
        if arr[i]>arr[i+1]:
            break
        i+=1
    l=(i+1)%n
    r=i
    while(l!=r):
        if arr[l]+arr[r]==target:
            return True
        elif arr[l]+arr[r]>target:
            r=(n+r-1)%n
        else:
            l=(l+1)%n
    return False

int findPairSum(vector<int> a, int x){
    int k=-1; //rotate point
    int n = a.size();
    //finding the rotate point
    for(int i=0; i<n-1; ++i){
        if(a[i+1]<a[i]) {
            k=i;
            break;
        }
    };
    //rotating to sort the array if not already sorted
    if(k != -1) rotate(a.begin(), a.begin()+k+1, a.end());

    //finally searching in sorted array
    int i=0, j=n-1;
    // sort(a.begin(), a.end());
    while(i<j){
        if(a[i]+a[j]==x) return 1;
        else if(a[i]+a[j]>x) --j;
        else ++i;
    }
    return 0;
}

int findPairSum(vector<int> arr, int target)

{

    //Write your code here

    int n=arr.size();

    int i;

    for(i=0;i<arr.size();i++)

        if(arr[i]>arr[i+1])

            break;

    int l=(i+1)%n;

    int r=i;

    while(l!=r){

        if(arr[l]+arr[r]==target)

            return true;

        if (arr[l] + arr[r] < target)

            l = (l + 1) % n;

        else

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

    }

    return false;

}