Introduction
Before diving into the problem, let’s understand the concept behind the sorted and rotated array for a clear vision. Unlike the standard arrays, the elements are stored in ascending or descending order in a sorted array.
For example:
We all know rotating means shifting something from its original place to a specific location. Like in school days, we used to rotate( or shift) our seats the same way as we rotate the array elements in clockwise or anti-clockwise orientation. We can rotate the array elements as many times as we want.
For example- Rahul has rotated the array 3 times, as shown below:
This is how the rotation takes place in the case of arrays. Now, let’s figure out the approaches we can think of while dealing with the sorted and rotated arrays using the problem given below.
You are given a sorted array that has been rotated around an unknown point. Determine whether the array contains a pair with the supplied sum ‘X.’ It is reasonable to presume that all array elements are distinct.
Examples:
Input arr[ ] = { 3, 6, 8, 16, 19 }
X = 14 ( target sum )
OUTPUT = true
Explanation = The pair ( 6 , 8) with sum 14.
Input arr[ ] = { 5, 8, 30, 90 }
X = 20 ( target sum )
OUTPUT = false
Explanation = No pair with sum 20.
It is recommended to try the stated problem on your own before proceeding with the solution.
Approaches
In this article, we will be looking forth into the two methods to encounter the stated problem.
- Brute force approach
- Two-pointer approach
Let’s start with the ideas:
Method 1: Brute Force approach
A simple solution can be iterating over all the possible pairs then comparing the pair sum with the target sum. However, it is not an optimum approach because we are looping through all potential pairs, which increases the program’s time complexity.
We will need two loops to execute this approach where the outer one will pick one element, and the inner one will couple the selected element with all of its following elements one by one. Later on, the pair’s sum will be compared with the target sum. If matches, return 1, otherwise check for the next pair. Repeat this process until the end of the array is encountered. If no pair has a sum equivalent to the target sum, then return 0.
Let’s see the implementation of the above approach:
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
void hasPairSum(int A[], int target, int n){
int sum=0;
for(auto i=0;i<n;i++){
for(auto j=i+1;j<n;j++){
sum = A[i]+A[j];
// if matches the target sum
if(sum == target){
cout<<"A pair exists with the given target sum: "<<A[i]<<" and "<<A[j]<<"\n";
return;
}
}
}
// if not found any pair
cout<<"There does not exist any pair with the given target sum\n";
return;
}
int main(){
int target,size;
cout<<"Enter the target sum:\n";
cin>>target;
cout<<"Enter the size\n";
cin>>size;
int A[size];
// User input
cout<<"Enter the elements:\n";
for(int i=0;i<size;i++){
cin>>A[i];
}
hasPairSum(A,target,size);
return 0;
}
Input
Enter the target sum: 12 Enter the size 4 Enter the elements: 8 5 6 7
Output
A pair exists with the given target sum: 5 and 7
Explanation: We iterated through each element, then used an inner loop to build a pair with the elements afterwards. The pair was printed, and 1 was returned to the calling statement since the pair sum was equal to the desired target.
Pictorial Representation:
Time Complexity:- O(n^2), where n is the number of elements. We have a poor solution since we employed two loops that run nearly equivalent through all elements.
Space Complexity:- O(1), i.e., constant space.
Method 2: Using a two-pointer approach
In general, A two-pointer strategy is an approach in which two pointers, as the name implies, point to some indexes. The first will point to the beginning of the array, while the second will point to the end. However, it is required for the array to be in a sorted form to implement the two-pointer approach.
These two pointers can now be used to loop through the elements of a sorted array. The method returns 1 if the total sum of the values at pointer1 and pointer2 equals the target sum.
If the total is less than the target sum, the pointer 1 will be incremented by one.
Pointer 2 will be decremented by one to reach the target if the total exceeds the target sum.
This idea will be carried on until both the pointers collide.
To have a better understanding of the two-pointer technique, try implementing the described approach on your own.
This approach only applies to the sorted array. We can use the same method for rotated arrays but with some minor changes.
Approach for the rotated arrays:
The aim is to find the largest element in the array first, serving as the pivot point, and then the smallest element. We apply a similar approach in the middle procedure (as stated for the sorted array above) to see a pair. Once we have indexes for the largest and smallest items in an array, the only new update is that indexes are rotated when they are increased and decremented using modular arithmetic.
Algorithm:
Step 1:- Find the sorted and rotated array’s pivot element. The pivot element is the largest in the array. In a sorted and rotated array, the smallest element will be adjacent to the pivot element.
Step 2:- Use two pointers (for example, left and right), with the left pointing to the smallest element and the right referring to the largest.
Step 3:- Compare the pair sum with the target sum. If matches return 1, otherwise jump to step 4.
Step 4:- If the pair sum is less than the target sum, then to increase the sum, move the left pointer to the next position by incrementing it rotationally.
Step 5:- If the pair sum is greater than the target sum, then to decrease the sum, move the right pointer to the next position by decrementing it rotationally.
Step 6:- Repeat the 3,4 and 5 steps until both the pointers collide.
Implementation:
#include <bits/stdc++.h>
using namespace std;
// This function returns true if arr[0..size-1] has a pair
// with sum equals to the target sum.
void pairInSortedRotated(int arr[], int n, int target)
{
// Find the pivot(largest) element
int i;
for (i = 0; i < n - 1; i++)
if (arr[i] > arr[i + 1])
break;
int low = (i + 1) % n; // l is now the index of smallest element
int high = i; // r is now index of largest element
// Keep moving either low or high till they meet
while (low != high)
{
// return true if we find a pair satisfying the condition
if (arr[low] + arr[high] == target)
{
cout << "A pair exists with the given target sum: " << arr[low] << " and " << arr[high] << "\n";
return;
}
// If current pair sum is less, increment the low pointer
if (arr[low] + arr[high] < target)
low = (low + 1) % n;
// Move to the lower sum side
else
high = (n + high - 1) % n;
}
cout << "There does not exist any pair with the given target sum\n";
return;
}
int main()
{
int size, target;
cout << "Enter the size of the array:\n";
cin >> size;
int arr[size];
cout << "Enter the array elements:\n";
for (int i = 0; i < size; i++)
{
cin >> arr[i];
}
cout << "Enter the target sum:\n";
cin >> target;
pairInSortedRotated(arr, size, target);
return 0;
}
Input
Enter the size of the array: 4 Enter the array elements: 8 5 6 7 Enter the target sum: 12
Output
A pair exists with the given target sum: 5 and 7
Time Complexity: O(n), where n is the number of elements. This solution can be optimized if the largest or pivot element is being searched using the binary search, which takes O(logn), however the overall time complexity will still be O(n) as we use the two-pointer approach.
Space Complexity:- O(1), i.e., constant space.
Pictorial Representation:
Try to implement the same approach for duplicate elements on your own.
Frequently Asked Questions
An array’s rotation simply means shifting the array’s elements to the specified places. We can rotate an array in both clockwise and anticlockwise ways. An array can be rotated an infinite number of times.
Using binary search, an element in a sorted array can be found in O(log n) time.
An array can be rotated an infinite number of times.
In the two-pointer approach, pointers refer to an array’s indexes. Using pointers, we can process two elements per loop instead of just one: two pointers, each starting from the beginning and the end until they collide.
Key Takeaways
We learned about the different methods for finding the pair sum in a sorted and rotated array that matches the target sum in great detail to recap the subject. To have a better understanding, use your hands and tackle the given challenges on Code Studio. In addition, evaluate each technique and try to code in your preferred language.
Enroll in one of our top-notch courses to ensure a prosperous future.
Ninja, have fun learning!
By: Alisha Chhabra
