Here’S A Quick Way To Solve The Pairs Hackerrank Problem

In This post we are going to discuss the Pairs Hackerrank Solution .

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

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

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

  • 2 <= Size of Array <= 10⁵
  • 0 < k < 10⁹
  • 0 < arr[i] <= 2³¹ -1

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.

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:

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:

The Solution is great but it will lead to timeout when all test cases are run,because of the constraints we have size of the array as 10⁵


You can see in the code that we have used nested loops so that will take O(n2) Time Thus it will Lead to Timeout.

All Test Cases:

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.

Hope You Like It. Thank You For Reading!

A Website To Learn Coding,Get Mini Projects With Implementations ,Competitive Programming ,HackerRank Solutions.@ https://codeityweb.blogspot.com