Let me quickly explain the problem

originally from here:

Sample input is:

5 2  
1 5 3 4 2

referencing the above input

first line:

N = 5, K = 2 

where N is the number of integers in the set, and K is the difference we are looking for

second line (as an array):

[1, 5, 3, 4, 2];

How many pairs in the array have a difference of K ?

sample answer: "There are 3 pairs of integers in the set with a difference of 2."

here is something I'm working on for this, but I am missing something :

function findDifference(k, nArr) {

    nArr.sort((a, b) => a - b);

var pairsWithDifferenceOfK = 0;

for (var i = 0; i < nArr.length; i++) {
    if (Math.abs((nArr[i] - ((nArr.length > (i + k)) ? nArr[(i + k)] : nArr[i]))) === k) {
       pairsWithDifferenceOfK++;
   };
}
   console.log(pairsWithDifferenceOfK);
}
var K = 2;
Arr = [1, 5, 3, 4, 2];
findDifference(K, Arr);

output:

3

This fails when given these inputs ( and I am curious as to why this fails on some inputs and not others):

10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 42804763 491595254 879792181 1069262793

Let me quickly explain the problem

originally from here: https://www.hackerrank./challenges/pairs

Sample input is:

5 2  
1 5 3 4 2

referencing the above input

first line:

N = 5, K = 2 

where N is the number of integers in the set, and K is the difference we are looking for

second line (as an array):

[1, 5, 3, 4, 2];

How many pairs in the array have a difference of K ?

sample answer: "There are 3 pairs of integers in the set with a difference of 2."

here is something I'm working on for this, but I am missing something :

function findDifference(k, nArr) {

    nArr.sort((a, b) => a - b);

var pairsWithDifferenceOfK = 0;

for (var i = 0; i < nArr.length; i++) {
    if (Math.abs((nArr[i] - ((nArr.length > (i + k)) ? nArr[(i + k)] : nArr[i]))) === k) {
       pairsWithDifferenceOfK++;
   };
}
   console.log(pairsWithDifferenceOfK);
}
var K = 2;
Arr = [1, 5, 3, 4, 2];
findDifference(K, Arr);

output:

3

This fails when given these inputs ( and I am curious as to why this fails on some inputs and not others):

10 1
363374326 364147530 61825163 1073065718 1281246024 1399469912 42804763 491595254 879792181 1069262793

• javascript
• algorithm

• sorry, editing now – Alex Anderson Commented Dec 11, 2016 at 9:13
• What is purpose of N? – guest271314 Commented Dec 11, 2016 at 9:18
• They give it as part of the input, however since N is just the number of ints supplied in the input, I just use the length of the array for this value. Let me edit that – Alex Anderson Commented Dec 11, 2016 at 9:21
• 1 What's the purpose of using the target difference k at the index..? – Redu Commented Dec 11, 2016 at 9:26
• @Redu thank you for your help! but sorry, could you be more specific with where you mean target difference of k? – Alex Anderson Commented Dec 11, 2016 at 9:55

7 Answers 7

One way to solve this could be with recursion. In each iteration of function you can take first element and then pare it to rest of elements. So for example you you start with

var rest = arr.splice(1);

where rest is [5, 3, 4, 2] and you pare each element to 1 and then you pass rest to function where you pare [3, 4, 2] to 5 etc... Then you check on each element if difference is k and if it is you increment result. When arr parameter bees empty array function will exit or return 1.

var K = 2;
var array = [1, 5, 3, 4, 2];

function findDifference(k, arr) {
  var r = 0;

  function inner(k, arr) {
    if (!arr.length) return 1;
    var rest = arr.splice(1);

    rest.forEach(function(e) {
      if (Math.abs(arr[0] - e) == k) r++;
    })

    inner(k, rest);
  }
  inner(k, arr);
  return r;
}

console.log(findDifference(K, array));

A near linear solution implemented in JavaScript through Set is below:

function pairs(k, arr) {
  const points = new Set(arr);
  let pairs = 0;
  for (let i = 0; i < arr.length; i++) {
    if (points.has(arr[i] - k)) {
      pairs++;
    }
  }
  return pairs;
}

console.log(pairs(2, [1, 5, 3, 4, 2]));

Assuming that Set will return the existence of element in O(1) time

I propose you to fill an array with binations of pairs and removing those which don't match with K. Then you would just have to return the length of final array :

var findDifference = (array, K) => {
  var pairs = [];
  array.forEach((x, i, arr) => arr.slice(i+1).forEach(y => pairs.push([x, y])));
  return pairs.filter(x => Math.abs(x[0]-x[1]) === 2).length;
}

console.log(findDifference([1, 5, 3, 4, 2], 2));

You can do as follows;

function countTargetDiff(ar,td){
  return ar.reduce((p,c,i,a) => p += a.slice(i+1).filter(f => Math.abs(c-f) === td).length,0);
}
arr = [1, 5, 3, 4, 2],
  k = 2,
res = countTargetDiff(arr,k);

console.log(res);

You can use for loop, Array.prototype.filter(), Array.prototype.slice() to pare each element of array to remainder of array.

var array = [1, 5, 3, 4, 2];
var n = 0;

for (var i = 0, j = 2; i < array.length; i++) {
  if (i + 1 < array.length) {
    var curr = array[i];
    var not = array.slice(i + 1).filter(function(el) {
      return el !== curr;
    });
    var diff = not.filter(function(el) {
      return el - curr === j || curr - el === j
    });
    if (diff.length) {
      n += 1
    }
  }
}

console.log(n)

The problem with this challenge is that the tests case 10 to 14 are using a lot of numbers, so you have to find an efficient way to avoid the timeout problem.

Another way to solve this is to pare every time two numbers in a sorted array, according to their difference.

Basically if the difference between numA and numB is less than K you know that you have to find a bigger number by moving to the right with numB. If your difference is bigger than K, you know you have to reduce the gap by looking for a bigger numA.

const n = 5, k = 2, numbers = [1, 5, 3, 4 ,2]
numbers.sort((a, b) => a - b); //increasing order

let index1 = 0, index2 = 1, pairs = 0;
while (index2 < n) {
  let difference = numbers[index2] - numbers[index1];
  if (difference === k) (pairs++, index2++);
  if (difference < k) index2++;
  if (difference > k) index1++;
}
console.log(pairs === 3);

This way you decrease a lot the number of operations and so the worst plexity. You should pass all the 16 tests case for this challenge with this.

    function pairs(k, arr) {
    let numberOfPairs = 0;
    let sorted = arr.sort((numA, numB) => numA - numB);
  
    for(let i=0; i < sorted.length; i++) {
        for(let j= i + 1; j < sorted.length; j++) {
          let difference = sorted[j] - sorted[i]
            if(difference === k) {
               numberOfPairs++;
               break
            } if(difference > k) {
              break
            }
        } 
    }
   return numberOfPairs;