Deadly Nicotine - 1 year ago 56
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?

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();
}
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download