Last Updated: 12 Jan, 2021

Check Difference

Easy

Asked in company

Solve now

Problem statement

You are given an array 'ARR' of 'N' integers and a non-negative integer 'K'. Your task is to find if there exists two indices 'i' and 'j' such that ARR[i]-ARR[j] = K, given 'i' is not equal to 'j'. If there exist such indices you have to return TRUE else you have to return FALSE. According to the return value, ‘YES’ or ‘NO’ will be printed, ‘YES’ for TRUE and ‘NO’ for FALSE.

For example :

1. ARR = [5,3,7,1] and K=2
We can see for i=1 and j =2, ARR[i]-ARR[j] = 2 .
So we will return TRUE.
2. ARR = [-2,7,3,1,5] and K=10
We can see for any two indices it is not possible that the difference in their value is equal to K.
So we will 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.
The second line contains 'N' space-separated distinct integers a1, a2, ..., aN — the array elements.

Output format:

For each test case print ‘YES’ if there exists a pair of indices with difference 'K' else return ‘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.

Constraints

1<= T <=100
1 <= N <= 10^5
-10^5 <= ARR[i] <= 10^5

Where 'T' denotes the number of test cases, 'N' denotes the number of elements in the array ‘ARR’ respectively, and 'ARR[i]' denotes the 'i-th' element of the array 'ARR'. 

Time limit: 1 second

Solve now

Approaches

01 Approach

The idea is to check the difference of all possible pairs or we can say for a given i we will check all possible values of j. More formally we can run two nested loops where outer loops will iterate over i and inner loop will iterate over j.

Iterate over ARR[i] for each 0 <= i < N and do:
1. Iterate over ARR[j] for each i+1 <= j < N and do:
  1. If (ARR[i] - ARR[j]) or (ARR[j]-ARR[i]) is equal to K then return ‘YES’ and stop iterating.
Return ‘NO’ if we have completed the iteration as we still have not found suitable i and j.

Solve now

02 Approach

The idea is to first sort the array. Then let’s say if we are at index i then we need to search for value ARR[i]+K, and now we can do this task in log(N) using binary search as the array is already sorted.

Iterate over ARR[i] for each 0 <= i < N and do:
1. Initialize an integer variable REQ=ARR[i]+K, representing the element we need to search.
2. Initialize an integer variable LOW=i+1, representing a lower limit of binary search.
3. Initialize an integer variable HIGH=N-1, representing an upper limit of binary search.
4. Repeat this step while LOW<=HIGH :
  1. Set MID = (LOW+HIGH)/2
  2. If ARR[MID] = REQ then return TRUE( as we find the element).
  3. If ARR[MID] > REQ then set HIGH=MID-1 ( we are discarding the right half).
  4. If ARR[MID] < REQ then set LOW=MID+1 ( we are discarding the right half).
Return FALSE, as if we can not find 2 suitable indices.

Solve now

03 Approach

We will scan the array from left to right and we will use the Hash to store all previously encountered elements. Whenever we encounter an element we will set its hash value to 1.

Now if we are at index i then we will find two value

ARR[i]-K says REQ1 (When another element is smaller than ARR[i]).
ARR[i]+K say REQ2 (When another element is larger than ARR[i]).

Now we just need to find whether we previously encountered REQ1 or REQ2, if yes then we can return ‘YES’.

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 0 <= i < N and do:
1. REQ1 = ARR[i] - K.
2. REQ2 = ARR[i] + K.
3. If REQ1 or REQ2 exists in MYMAP then return ‘YES’.
4. Set the hash value of ARR[i] as 1, MYMAP[ARR[i]] = 1.
Return ‘NO’.

Solve now