Problem of the day
New update is available. Click here to update.
Last Updated: 12 Jan, 2021
Check Difference
Easy
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
Approaches
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:
- Iterate over ARR[j] for each i+1 <= j < N and do:
- If (ARR[i] - ARR[j]) or (ARR[j]-ARR[i]) is equal to K then return βYESβ and stop iterating.
- Iterate over ARR[j] for each i+1 <= j < N and do:
- Return βNOβ if we have completed the iteration as we still have not found suitable i and j.
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:
- Initialize an integer variable REQ=ARR[i]+K, representing the element we need to search.
- Initialize an integer variable LOW=i+1, representing a lower limit of binary search.
- Initialize an integer variable HIGH=N-1, representing an upper limit of binary search.
- Repeat this step while LOW<=HIGH :
- Set MID = (LOW+HIGH)/2
- If ARR[MID] = REQ then return TRUE( as we find the element).
- If ARR[MID] > REQ then set HIGH=MID-1 ( we are discarding the right half).
- 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.
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:
- REQ1 = ARR[i] - K.
- REQ2 = ARR[i] + K.
- If REQ1 or REQ2 exists in MYMAP then return βYESβ.
- Set the hash value of ARR[i] as 1, MYMAP[ARR[i]] = 1.
- Return βNOβ.
Similar problems
Download our app:
FOLLOW US ON
We accept payments using:
