Deadly Nicotine - 2 months ago 9

C# Question

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`

Let me explain how I think it works. If we have

`arr={1,1,1,2,3,3,5}`

`K=2`

`counter`

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

Let

`count = 0`

I take the key

`1`

`1-K=-1`

`counter`

`count =`

`2`

For the key

`3`

`3-K=1`

`counter`

`3`

`1`

`counter[3]=1`

`2`

`count = 3*2 = 6`

By the same logic as above, we add one more to

`count`

`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();
}
```