Last Updated: 22 Feb, 2021
Ninja And The Dance Competetion
Easy
Asked in companies
Ninja has been asked to organize a dance competition. Ninja decided that he will take individual entries and then will divide them into pairs. As part of the entry, he asked the participants to choose any number.
Ninja then thought of a creative method to divide them into pairs. He decided that he would select a number ‘K’, and then select numbers from the list that have a difference equal to ‘K’.
You need to help Ninja in finding the number of distinct pairs from the numbers with differences equal to ‘K’.
Example:
Let us suppose the numbers are chosen by participants: [2, 6, 5, 2, 3] and K = 3, then the distinct pairs having differences equal to K are: [2, 5] and [3, 6] so print 2.
Note:
The list of numbers can contain duplicate numbers, you need to print only the distinct pairs.
For example [2, 2, 3, 4] and K = 1, so you need to print 2 as the two distinct pairs are: (2, 3) and (3, 4).
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases.
The first line of each test case will contain two space-separated integers ‘N’ and ‘K’, where ‘N’ denotes the number of elements of the array that contains the chosen numbers, and ‘K’ denotes the difference required between the pair elements.
The second line of each test case will contain ‘N’ space-separated integers denoting the chosen numbers by the participants.
Output Format:
For each test case, print a single integer that denotes the distinct pairs having differences equal to K.
Output for every test case will be printed in a separate line.
Constraints:
1 <= T <= 10^2
0 <= N <= 10^4
0 <= K <= 10^4
0 <= ARR[i] <= 10^9
Where ‘ARR[i]’ is the value of elements of the array.
Time Limit: 1 sec
Approaches
The brute force approach that we can think of is to check for every pair in the array and then count the number of pairs with a difference equal to ‘K’.
But this brute force approach will not be valid in the case of duplicates. So, in order to handle duplicate pairs, we will sort the array first and then find the pair and finally skip the ones that are equal.
Algorithm:
- Sort the given array in ascending order.
- Create a variable let’s say “count” to store the count of pairs.
- Now, we will use two pointer approach to compare the values:
- Let us say the pointers to be ‘a’ and ‘b’. Both start from ‘a’ = 0 and ‘b’ = 0
- Start a while loop until both the pointers reach the end of the array
- There will be three cases:
- If arr[b] - arr[a] > ‘K’
- The difference between element at ‘b’ and element at ‘a’ is greater than required, so to reduce it increment ‘a’.
- If arr[b] - arr[a] < ‘K’
- The difference between element at ‘b’ and element at ‘a’ is lesser than required, so to increase it increment ‘b’.
- If arr[b] - arr[a] == ‘K’
- Required pair found. Increment “count”, and skip similar elements for both ‘a’ and ‘b’.
- If arr[b] - arr[a] > ‘K’
- Return “count”.
In this approach, the basic is to store the frequency of elements and then check for the 2 basic cases of this problem.
We will use a Hashmap to store the frequencies. The two base cases of this problem are:
- If ‘K’ = 0
- If ‘K’ > 0
After creating the map we will move forward with these cases.
Algorithm:
- Create a Hashmap and store the frequency of every element present in the array.
- Initialize a variable “count” that will store the count of distinct pairs.
- Case 1: If ‘K’ = 0:
- Simply count the elements in the map that have a frequency greater than 1, which means count all the elements that appear more than once. Keep in mind that you need to count one element as one even if it gets repeated more than one time.
- Case 2: If ‘K’ > 0”
- In this case, we look for the only values in which the first number of the pair is less than the second number.
- We do this in order to avoid duplicates. So, now we just check if the map contains a value = ‘x’ + ‘K’, where ‘x’ is the first element
- If found increment “count”.
- Finally, return the “count".