Last Updated: 26 Dec, 2020

Find Pair Sum in Rotated and Sorted array

Easy

Asked in companies

Solve now

Problem statement

Alice and Bob always loved to play with arrays. Alice took a sorted array and rotated it clockwise for a certain number of times.

For example:

Alice took a sorted array = [4,6,8,10,11] and if she rotates it by 3, then the array becomes: [8, 10, 11, 4, 6].

After rotating a sorted array, Alice gave a number ‘K’ to Bob and asked him to search for a pair in an array whose sum is equal to K. Since Bob was busy preparing for his semester exams, he asked you to help him.

You are given an array of integers ARR and a number K. Your task is to find out whether there exists a pair in the array ARR with sum K or not. If there exists a pair then you can return TRUE else return FALSE;

Input Format:

The first line of input contains a single integer T, representing the number of test cases
Then the T test cases follow.

The first line of each test case contains a number N denoting the size of the array and an integer K representing the sum of pair.

The second line contains N space-separated distinct integers a1, a2, ..., aN — the array elements.

Output format:

For each test case print “YES” if Bob finds the pair else print “NO”.

The output of every test case will be printed in a separate line.

Note:

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Follow Up:

Can you do this in O(N) time, and without using any extra space?

Constraints

1<= T <=100
2 <= N <= 10000
-10^8 <= A[i] <= 10^8
-10^8 <= k <= 10^8

Time limit: 1 second

Solve now

Approaches

01 Approach

We will find all the possible pairs by iterating over the whole array N times. At any time if the sum of any pair is equal to K we will return TRUE else keep on iterating.

Let’s say we have a given array ARR and pair sum K.
Iterate over ARR[i] for each i from 0 to N and do:
- Iterate over ARR[j] for each j from i+1 to N and do:
  - Check if ARR[i] + Arr[j] is equal to K then return TRUE
Return FALSE.

Solve now

02 Approach

We will scan the array from left to right and we will use the Hash to store all previously encountered elements. So at each step, we find a value say REQ = k - (current element), and see if REQ already exists in Hash.

Let's say we have given an array ARR.
We are using an unordered_map called MYMAP as Hash.
Iterate over ARR[i] for each i from 0 to N and do:
- REQ = k - ARR[i]
- If REQ exists in MYMAP then return TRUE
- MYMAP[ARR[i]] = 1
Return FALSE

Solve now

03 Approach

We will find the index of the shortest element and as we know that the index of the largest element will always be 1 less than the index of the shortest element.

Now we can use two pointer technique to find the pair whose sum is k in a single scan. But we have to care that indices can go less than 0 or more than N - 1. So we will be using modular operation (IDX % N where IDX is an index of the array) to always keep indices in the valid range.

Let's say we have given an array ARR.
We are going to find the index of the smallest element, say PIVOT.
LOW = 0 , HIGH = N - 1
While LOW is less than HIGH do:
- MID = (LOW + HIGH) / 2
- If ARR[MID] is greater than ARR[MID + 1]:
  - Put PIVOT = MID + 1 and break from the loop.
- Else If ARR[MID - 1] is greater than ARR[MID]:
  - Put PIVOT = MID and break from the loop.
- Deciding in which direction we should go as one part will always be sorted
- If ARR[MID] is less than ARR[HIGH]:
  - Put HIGH is equal to MID - 1 ( as Right part is sorted)
- Else:
  - LOW is equal to MID + 1 (Left part is sorted)
After the above step, we will have a PIVOT element.
In the following steps, we will run TWO POINTER techniques to find the pair.
LOW = PIVOT, HIGH = PIVOT - 1
While LOW is not equal to HIGH do (also we have to take care of keeping LOW and HIGH in range by taking mode with N):
- TEMP = ARR[LOW] + ARR[HIGH]
- If TEMP is equal to K then return TRUE.
- If TEMP is less than K, we need to increase the value of TEMP so increase LOW by 1.
- Else we need to decrease the value of TEMP so decrease HIGH by 1.
If we do not get a solution in step 8 we can safely return FALSE.

Solve now