Check Difference

Easy
0/40
Average time to solve is 15m
profile
Contributed by
29 upvotes
Asked in company
Facebook

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample input 1:
4
5 3
4 3 2 1 5
3 7
6 1 3 
7 12
-3 5 -2 4 1 0 9
5 2
12 22 1 2 8
Sample output 1:
YES
NO
YES
NO
Explanation for sample output 1
(i) The possible indices are i=1 and j=4.
(ii) There do not exist 2 indices that satisfy the criteria.
(iii) The possible indices are i=7 and j=1.
(iv) There do not exist 2 indices that satisfy the criteria.
Sample input 2:
3
4 1
2 4 6 8 
5 0
5 4 5 3 1
7 10
-10 2 5 3 2 1 0
Sample output 2:
NO
YES
YES
Explanation for sample output 2:
(i) There do not exist 2 indices that satisfy the criteria.
(ii) The possible indices are i=1 and j=3.
(iii) The possible indices are i=7 and j=1.
Hint

Check all the pairs of indices.

Approaches (3)
Brute Force

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.

  1. 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.
  2. Return ‘NO’ if we have completed the iteration as we still have not found suitable i and j.
Time Complexity

O(N^2), where N is the length of the string.

 

For each element, we are iterating over the whole array. So for N elements iterating N times. Hence, the overall time complexity is O(N^2).

Space Complexity

O(1).

 

We are not using any extra memory. Hence, the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Check Difference
Full screen
Console