Deadly Nicotine Deadly Nicotine - 1 month ago 4
C# Question

Find the number of pairs in an array whose difference is K?

So basically what I'm trying to do is

static int NumdiffExponential(int[] arr, int K)
{
return (from i in arr
from j in arr
where (j - i) == K
select 1).Count();
}


except in linear time, preferably with a single LINQ query and in a way that is compact, readable and micro-optimal. So what I came up with is the attempt

static int NumdiffLinear(int[] arr, int K)
{
var counters =
arr
.GroupBy(i => i)
.ToDictionary(g => g.Key, g => g.Count());
return
counters
.Keys
.Aggregate(
0,
(total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)
);
}


which keeps coming out as
0
and I can't figure out why.

Let me explain how I think it works. If we have
arr={1,1,1,2,3,3,5}
and
K=2
, then the
counter
is like

1->3, 2->1, 3->2, 5->1


Let
count = 0
.

I take the key
1
and see that
1-K=-1
is not a key in
counter
and therefore
count =
0 still. Same with the key
2
.

For the key
3
we have
3-K=1
which is a key in
counter
. There are
3
occurrences of the key
1
(i.e.
counter[3]=1
and 2 occurrences of the key
2
. Therefore
count = 3*2 = 6
because of the pairs (1,3),(1,3),(1,3),(1,3),(1,3),(1,3),(1,3) which can be formed.

By the same logic as above, we add one more to
count
because of the pair (3,5). So the answer is
count = 7
.

Anything wrong with my algorithm or the implementation of it?

Answer

More readable and much more compact:

static int NumdiffLinear(int[] arr, int K)
{
    return arr.SelectMany(v => arr, (a, b) => new { a, b })
                .Where(s => s.b - s.a == K)
                .Count();
}

Here is a linear one with the same principle:

static int NumdiffLinear(int[] arr, int K)
{
    int n = 1;
    return arr.Select(value => new { value, index = n++ }) //Get number and index
                .SelectMany(indexValue => arr.Skip(indexValue.index), (a, b) => new { a = a.value, b }) //Project it with the next elements in the array
                .Where(s => s.a - s.b == K) //Do the math
                .Count();
}
Comments