Pair with given sum in rotated array

Given an array arr[] of distinct elements, with size N, which has been sorted and subsequently rotated around an unknown pivot point. Our objective is to determine whether the array contains a pair whose elements sum up to a given value X.

Example

Input: arr[] = {13, 15, 6, 8, 9, 11}, X = 17
Output: true
Explanation: There is a pair (6, 11) with sum 17

 Code Approach 1

## Java Code

public class PairWithGivenSumInRotatedArray {
    public static boolean hasPairWithSum(int[] arr, int sum) {
        int n = arr.length;
        
        // Find the pivot point
        int pivot = findPivot(arr, 0, n - 1);
        
        // left points to the minimum element
        int left = pivot;
        // right points to the element just before the minimum element
        int right = (pivot - 1 + n) % n;
        
        // Two-pointer approach to find the pair with sum X
        while (left != right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum == sum) {
                return true;
            } else if (currentSum < sum) {
                left = (left + 1) % n;
            } else {
                right = (right - 1 + n) % n;
            }
        }
        
        return false;
    }
    
    // Function to find the pivot point (index of the minimum element)
    private static int findPivot(int[] arr, int low, int high) {
        // If array is not rotated, return 0
        if (arr[low] < arr[high]) {
            return 0;
        }
        
        while (low <= high) {
            int mid = (low + high) / 2;
            int next = (mid + 1) % arr.length;
            int prev = (mid + arr.length - 1) % arr.length;
            
            if (arr[mid] <= arr[next] && arr[mid] <= arr[prev]) {
                return mid;
            } else if (arr[mid] <= arr[high]) {
                high = mid - 1;
            } else if (arr[mid] >= arr[low]) {
                low = mid + 1;
            }
        }
        return -1; // Should not reach here
    }
    
    public static void main(String[] args) {
        int[] arr = {7, 9, 11, 15, 1, 3, 5};
        int sum = 10;
        
        System.out.println("Does the array have a pair with sum " + sum + "? " + hasPairWithSum(arr, sum));
    }
}

Output

Does the array have a pair with sum 10? true

Algorithm Approach 2

1. Initialization of Pointers:

   • Initialize two pointers, left and right, initially pointing to the first and last elements of the array, respectively.

2. Loop Execution:

   • Enter a loop that continues as long as left is less than right.

3. Current Sum Calculation:

   • Calculate the current sum of the elements pointed to by left and right.

4. Comparison with Target Sum:

   • Compare the current sum with the target sum, X. There are three possibilities:
     • If the current sum is equal to X, return true because a pair with the given sum has been found.
     • If the current sum is less than X, increment the left pointer (move it to the right) to potentially increase the sum.
     • If the current sum is greater than X, decrement the right pointer (move it to the left) to potentially decrease the sum.

5. Loop Termination:

   • Continue the loop until one of the following conditions is met:
     • A pair with the sum X is found, in which case you return true.
     • Both pointers (left and right) cross each other or are adjacent, indicating that there are no pairs in the array with the sum X. In this case, return false.

Complexity Approach 2

• Time Complexity: O(log n), where 'n' is the length of the input array
• Space Complexity: O(1),  because the code uses a fixed number of variables

Code Approach 2

## Java Code

public class PairWithSumInRotatedArray {
    public boolean hasPairWithSum(int[] arr, int X) {
        int n = arr.length;
        int left = 0;
        int right = n - 1;

        while (left < right) {
            int currentSum = arr[left] + arr[right];

            if (currentSum == X) {
                return true; // Pair found with the given sum X
            } else if (currentSum < X) {
                left++; // Move the left pointer to the right
            } else {
                right--; // Move the right pointer to the left
            }

            // If both pointers cross, no pair is found
            if (left == right) {
                break;
            }
        }

        return false; // No pair found with the given sum X
    }

    public static void main(String[] args) {
        PairWithSumInRotatedArray solution = new PairWithSumInRotatedArray();
        int[] arr = {11, 15, 26, 38, 9, 10};
        int X = 35;
        boolean result = solution.hasPairWithSum(arr, X);
        System.out.println("Has pair with sum " + X + ": " + result);
    }
}

Output

Has pair with sum 35: true