2 Ways To Solve The Pairs Hackerrank Problem - KodeSrc

 

Pairs Hacker rank Solution

The Problem is as Follows:

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

For example, given an array of [1, 2, 3, 4] and a target value of 1, we have three values meeting the condition: 2-1=1, 3-2=1 , 4-3=1



Function Description:

Complete the pairs function below. It must return an integer representing the number of element pairs having the required difference.

pairs has the following parameter(s):

k: an integer, the target difference
arr: an array of integers



Constraints:

• 2 <= Size of Array <= 10^5

• 0 < k < 10^9

• 0 < arr[i] <= 2^31 -1

Question Definition In Short:

Find the total number of pairs (two items) whose difference is equal to K. You will be given an unsorted array of integers and a variable K.

Solution:



1st Method:

The first answer is straightforward and will probably be the one you come up with quickly. It may be as simple as comparing every pair in the array, calculating their difference, and then counting up from there if it equals K.

• [3,4,2,6] array with K=2 
•  We compare each element in the array with every other element to determine how they differ before scanning the array.  
• Hence, Element 1 is 3. The absolute value of |(3-4)|=1 when we compare the remaining items, and it does not equal K=2. We so compare it to the following element, which is 2.
•  In contrast to the next, |3-6|=3, |3-2|=1 is not equivalent to K. incomparable to K.  
• We then infer that element 3 does not create pairs, and we go on to element 4, which is the following element.   
• When comparing 4 and 2, use the formula 4 2 to get 2. Count=1 and is equal to K, hence the counter is increased by 1.   
• Subsequent element |4-6|=2 equal to K, count equal to 2, counter increased by 1.   
• With Element 4, two pairs are thus produced.
  

• Now Element 2 , |2-6|=4 Not Equal To K , counter remains same Count =2.

• Next Element is 6 No more element to compare Thus we Stop Here.

• Thus Their are Two Pairs (4,2) and (6,4) whose difference is K=2.

Now Lets Code it and see What we get:



Pairs Hackerrank Solution Java:

 static int pairs(int k, int[] arr) {

        int count = 0;

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (Math.abs(arr[i] - arr[j]) == k) count++;
            }
        }

        return count;
    }

We test it On Test Cases:






All Test Cases:



Solution 2:

It is difficult in beginning to come up to the best solution, but you
have to first try to solve the question, and then try to optimized it.
Solution:


Notably, the question does not specify that the pairs must be in chronological sequence, so [4,2,6] we are free to create a pair that has the same numbers (4,2) and (2,4).
This implies that we can now change the array to lower the time complexity.

• Initially, sort the array. 
•  Now, take two pointers: one that points to the first element and the other that points to the second. 
• Run a loop and determine whether there is a greater difference between the two elements. If so, the pair will be on the array's right side. Thus, increment the initial pointer and carry on with the loop. 
• We shift our second pointer if it is not greater than since it indicates that the pair is between the first pointer and another element that is not included by our second pointer. 
• We now increase our count and the second pointer to continue looking for further pairings if it is not greater nor smaller, which indicates that it is equal to K.

Pairs Hackerrank Solution Java:

    static int pairs(int k, int[] arr) {

        int count = 0;
        Arrays.sort(arr);
        int i = 0;
        int j = 1;
        while (j < arr.length) {


            if (arr[j] - arr[i] > k) i++;
            else if (arr[j] - arr[i] < k) j++;
            else {
                count++;
                j++;
            }


        }
        return count;
    }

Output:





Pairs Hackerrank Solution Python:

def pairs(k, arr):
    count = 0
    arr.sort()

    i = 0
    j = 1

    while j < len(arr):
        if arr[j] - arr[i] > k:
            i += 1
        elif arr[j] - arr[i] < k:
            j += 1
        else:
            count += 1
            j += 1
    return count
 

 

Output:


Since we sorted the array first, the second solution works because sorting algorithms like Merge Sort and Quick Sort have an O(nlogn) time complexity.
and loop through the element to get an O(nlogn) overall time complexity, which is less than the prior one.


To sum up:

Telling them the first solution is a smart idea if the question comes up during an interview or other situation.
If they requested optimization, you may attempt explaining the other solutions to them.