Pair Difference K

Moderate

0/80

Average time to solve is 15m

13 upvotes

Asked in companies

Problem statement

You are given a sorted array ARR of integers of size N and an integer K. You have to find whether it is possible to find a pair of integers having an absolute difference of K.

Note:

1. K is a non-negative integer.

2. Absolute Difference between two integers A and B is equal to the difference of maximumOf(A, B) and minimumOf(A, B).

3. Pair of integers should have different indices in the array.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer T, denoting the number of test cases.

The first line of each test case consists of two space-separated integers N and K, denoting the size of the given array ARR and the required absolute difference.

The second line of each test case consists of N space-separated integers denoting the elements of the array.

Output format:

For each test case print, “Yes” if it is possible to have a pair of integers having absolute difference equal to K and “No” otherwise, 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^4
1 <= ARR[i] <= 10^9
0 <= K <= 10^9

Time Limit: 1 sec.

Sample Input 1:

1
3 2
1 2 3

Sample Output 1:

Yes

Explanation of sample input 1:

In the given array absolute difference of 1 and 3 equals to 2, which is required K.

Sample Input 2:

1
4 6
2 3 3 5

Sample Output 2:

No

Explanation of sample input 2:

As there is no pair of integers present in the given array whose absolute difference is K (which is 6 here).

Hint 1

Hint 2

Hint 3

Check for all possible pairs of integers in the array, if the absolute difference is K or not.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Solution

Iterate through the array ARR (with for loop variable i), consider this as one of the possible element in pair and let’s call it A(A = ARR[i]).
For each element A, iterate through the array ARR(with for loop variable j), consider this as the possible other element in the pair along with A. And let’s call it B(B = ARR[j]). But if i is equal to j then you cannot make this pair, hence move forward and try other pairs.
If the absolute difference between A and B (|A-B|), is equal to K, then we get the required pair and we can print “Yes”.
If after trying all possible pairs in the array we are unable to find the required pair we simply print “No”.

Time Complexity

O(N^2), where N is the size of the given array.

As there are N^2 different pairs possible in the array of size N, hence this will take the time of order O(N^2).

Space Complexity

O(1), as we are using constant extra memory.

(100% EXP penalty)

Pair Difference K

Console