CODEWITHSUNDEEP
c#.netalgorithmlinqtime-complexity
Deadly Nicotine
Deadly Nicotine

Reputation: 663

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?

Upvotes: 4

Views: 1147

Answers (4)

Low Flying Pelican
Low Flying Pelican

Reputation: 6054

You can fix-up the your solution as follows,

public int NumdiffLinear(int[] arr, int K)
        {
            var dupsDictionary =
                arr
                    .GroupBy(i => i)
                    .ToDictionary(g => g.Key, g => g.Count());


            return dupsDictionary.Keys.Aggregate(
                0,
                (total, i) =>
                    total +
                    dupsDictionary.Keys.Where(key => i - key == K)
                        .Sum(key => dupsDictionary[key]*dupsDictionary[i]));
        }

Upvotes: 0

Gusman
Gusman

Reputation: 15151

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

Upvotes: 5

M.kazem Akhgary
M.kazem Akhgary

Reputation: 19149

You should add instead of subtract. for example you know you have key = 1 and K = 2. then you have to check if key = (1+2) exist or not.

In your O(n^2) algorithm you check J - I == K. now assume you have only I and K. Simple math just do J = K + I if the condition were true then J should exist.

(total, i) => total + counters[i] * (counters.ContainsKey(K + i) ? counters[K + i] : 0)

Upvotes: 1

v78
v78

Reputation: 2933

Replace 

(total, i) => total + counters[i] * (counters.ContainsKey(K - i) ? counters[K - i] : 0)

by

(total, i) => total + counters[i] * (counters.ContainsKey(i-K) ? counters[i-K] : 0)

Upvotes: 1

Related Questions