Find number of pairs with difference larger than or equal to given number

Question

I have a array/dict(HashMap) of positive integers. I need to find the number of pairs that have a absolute difference greater or equal to a given number, K.

import random
import time

#given number
k =  4

# List of 2,00,000 random numbers in range 0-1000
strength = [random.randrange(0,1000) for x in range(200000)]  
strength.sort()

# start clock
start1 = time.clock()

n = len(strength)

# count keeps track of number of pairs found
count = 0

for x in range(n):
    for y in range(x,n):

        if abs(strength[x] - strength[y]) >= k:
            # if found, all number from this point to the end will satisfy
            count += n-y
            # So no need to go to the end
            break

end1 = time.clock()
print(count)
print(end1-start1)

All the answers I find are for pairs less than or equal to a given number.

I need to find the number of pairs that have a absolute difference greater or equal to a given number, K.

Answer 1

Note that the total number of pairs is n * (n - 1) / 2, so if you can find the number of pairs with difference less than K, the number of pairs with difference greater than K is just n * (n - 1) / 2 - num_pairs_with_diff_less_than_K

The solution you provide is also correct (and well documented). If your question is how to adapt it to your case, then all you need to do is to use values of your HashMap (sorted) instead of the strength array.

Answer 2

You can get the 2 item combinations of the array and then filter / reduce them according to the difference.

One might do the job in JavaScript as follows;

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                 : [[c]]),[]);
};

function getAcordingToDiff(a,d){
  return a.combinations(2)
          .reduce((p,c) => Math.abs(c[0]-c[1]) >= d ? (p.push(c),p) : p  ,[]);
}

var arr = Array(30).fill().map((_,i) => i+1); // array from [1,...,30]
console.log(JSON.stringify(arr))
console.log(JSON.stringify(getAcordingToDiff(arr,25))); // diff >= 25

Explanation:

So in the heart of the above code obviously lies the Array.prototype.combinations function. For those who are not familiar with JS, this is just an ordinary function that we define under the Array object's prototype (so that now every array has access to this function like arr.combinations(n)) But let's use a more expressive language and refactor the above combinations array method into a generic function.

function combinations(a,n){
  var sa;
  return a.reduce(function(p,c,i,a){
                    if (n > 1) sa = combinations(a.slice(i+1), n-1).map(e => (e.push(c),e));
                    else sa = [[c]];
                    return p.concat(sa);
                  },[]);
}

So as you will notice combinations(a,n) is a recursive function which takes an array a and items count n. It works on the basis of keeping the first item of the input array and recursively invoking itself with one item shorter array, combinations(a.slice(i+1), n-1), and with one less items count up until n decrements to 1 in which case it starts it's return cycle with whatever remains from the input array and each item is wrapped in an array, sa = [[c]].

So on the return cycle of the recursive calls we take the resulting array and push the kept first element (remember -> It works on the basis of keeping the first item of the input array) into each item of the returned array (remember -> ...and each item is wrapped in an array, sa = [[c]]).

So that's it... You should be able to figure out yourself the details.

However in our application we are given an array of numbers and requested to obtain only the 2 item combinations with a certain difference. In this particular case we don't need to calculate all combinations and then filter them. We can do this on the way constructing our combinations. As the required difference value d gets bigger this will bring in a huge gain over filtering afterwards method, since now as d gets bigger we are eliminating more and more of the two item combinations, even before we generate them. And... let's hard-wire our code to work with 2 items only and merge everything in a single function. The performance results are below;

function getCombosWithDiff(a, d, n = 2){
  var sa;
  return a.reduce(function(p,c,i,a){
                    if (n > 1) sa = getCombosWithDiff(a.slice(i+1), d, n-1).reduce((r,e) => Math.abs(e[0]-c) > d ? (e.push(c),r.push(e),r)
                                                                                                                 : r, []);
                    else sa = [[c]];
                    return p.concat(sa);
                  },[]);
}

var arr = Array(100).fill().map((_,i) => i+1);
 result = getCombosWithDiff(arr,89);
console.log(JSON.stringify(arr));
console.log(JSON.stringify(result));

So that's it. I have tried the above code to list the 2 items combinations each with diff greater than 10 from an array of 1000 items. It takes like 5000 msecs in Chrome and 14000 msecs in FF. However as mentioned above, the more the diff value d gets bigger, the shorter it takes. e.g same array with diff 900 would resolve in just 1100msecs with Chrome and in 4000msecs with FF.

You can test and play here

Answer 3

Create a 1001-element array A of integers initialized to zeroes. Generate your random integers, and increment the appropriate index by 1 for each such integer. With some math, you could do this without generating 2,000,000 random integers, but it's not worth the complexity.

Create a second 1001-element integer B s.t. B[i] = A[0] + ... + A[i]

Answer is sum from i=0 to 1000-k of B[i] * (2,000,000 - B[i+k-1])