Pair with given sum in rotated array
Medium
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;
// Twopointer 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

Initialization of Pointers:
 Initialize two pointers,
left
andright
, initially pointing to the first and last elements of the array, respectively.
 Initialize two pointers,

Loop Execution:
 Enter a loop that continues as long as
left
is less thanright
.
 Enter a loop that continues as long as

Current Sum Calculation:
 Calculate the current sum of the elements pointed to by
left
andright
.
 Calculate the current sum of the elements pointed to by

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.
 Compare the current sum with the target sum, X. There are three possibilities:

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
andright
) cross each other or are adjacent, indicating that there are no pairs in the array with the sum X. In this case, return false.
 Continue the loop until one of the following conditions is met:
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
Thanks for feedback.