2 Ways To Solve The Pairs Hackerrank Problem | Codeityweb

Pairs Hackerrank

In This post we are going to discuss the Pairs Hackerrank 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:

You will be given a unsorted array of integers, and a variable K, you have to find the total number of pairs (2 elements) Whose Difference is Equal To K.

Solution:



1st Method:

The first solution is direct and it will be mostly the solution you will get in short time thinking, the solution could be we compare all pairs in the array and find the difference of them and check if it is equal to K and increment the count.

• Array [3,4,2,6] and K=2

• We scan the array by comparing every element with all remaining element and finding their difference.

• So 1st Element is 3 We compare it remaining elements so, Absolute value of |(3-4)|=1 and it is not equal to K=2. So we compare it with next element i.e 2 .

• |3-2|=1, Not equal to K,compare with next, |3-6|=3 Not equal to K.

• So We conclude that No pairs are formed with element 3 , now we move to next element i.e 4

• Compare 4 with 2 |4-2|=2 Is Equal to K thus increment counter by 1 , Count=1.

• Next element |4-6|=2 Equal to K , Counter increment by 1, Count=2.

• Thus 2 Pairs are formed with Element 4.

• 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:


It Is to be noted that it is not given in the question that the pairs should be in order, that means [4,2,6] we can make a pair of (4,2) and (2,4) both will be same.
That means We can now modify the Array to reduce the timecomplexity.

• First Sort the array.

• Now take 2 pointers one pointing to first element and 2nd pointing to second element.

• Run a loop and check if the difference between the two element is greater or not if it is greater, than it means the pair will be to the right side of the array. So Increment the first pointer and continue the loop.

• If it is not greater than it means that the pair is between the first pointer and other element that is not included by our second pointer, so we move our second pointer.

• Now if it is neither greater nor smaller that means it is equal to K, so we increment our count and the second pointer to keep searching for other pairs.

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:


The 2nd Solution works because we have first sorted the array,
time complexity for sorting O(nlogn) for Algorithm like Merge Sort
,Quick Sort.
And loop to traverse the element so overall time complexity is
O(nlogn)
which is less than previous one.


Conculsion:

If the Question is asked in interview or something it is good
to tell them the first solution.
And if they asked to optimized it then you can try to
tell them the other solutions.


Hope You Like It. Thank You For Reading!