CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21405

Understanding Count pairs in array whose sum is divisible by K

I am going through this link and came across the code for count of pairs divisible by k.

The approach used is:

An efficient approach is to use Hashing technique. We will separate elements into buckets depending on their (value mod K). When a number is divided by K then the remainder may be 0, 1, 2, upto (k-1). So take an array say freq[] of size K (initialized with Zero) and increase the value of freq[A[i]%K] so that we can calculate the number of values giving remainder j on division with K.

Below is the code for it:

public static int countKdivPairs(int A[], int n, int K) 
    { 
        // Create a frequency array to count 
        // occurrences of all remainders when 
        // divided by K 
        int freq[] = new int[K]; 
  
        // Count occurrences of all remainders 
        for (int i = 0; i < n; i++) 
            ++freq[A[i] % K]; 
  
        // If both pairs are divisible by 'K' 
        int sum = freq[0] * (freq[0] - 1) / 2; 
  
        // count for all i and (k-i) 
        // freq pairs 
        for (int i = 1; i <= K / 2 && i != (K - i); i++) 
            sum += freq[i] * freq[K - i]; 
        // If K is even 
        if (K % 2 == 0) 
            sum += (freq[K / 2] * (freq[K / 2] - 1) / 2); 
        return sum; 
    }

I understood the code flow line by line, but I did not understand how this logic in code is solving the problem statement.

Why we are doing these steps:

1) int sum = freq[0] * (freq[0] - 1) / 2; 
2) sum += freq[i] * freq[K - i]; 
3)             if (K % 2 == 0) 
                sum += (freq[K / 2] * (freq[K / 2] - 1) / 2);

Can you please provide an explanation?

Upvotes: 4

Views: 6823

Answers (1)

Serial Lazer
Serial Lazer

Reputation: 1669

The question is to find all the pairs whose sum is divisible by K.

Little background:

Hypothetically, assume that the pair (a, b) is one of those. So we have

(a + b) % K == 0

Lets assume:

a % K = p
b % K = q

where p & q could be any positive integers between [0, K-1].

But the important point is: do you think there is a relationship between p & q?

Yes, there is; because a+b % K == 0

a = xK + p
b = yK + q

**a + b = (x+y)K + (p+q)**

But we already know that a+b is divisible by K.
That clearly means:

p + q = K or p + q = 0 (remember that both p, q is within [0, K-1])

Back to your question:

1) int sum = freq[0] * (freq[0] - 1) / 2; 
2) sum += freq[i] * freq[K - i]; 
3)             if (K % 2 == 0) 
                sum += (freq[K / 2] * (freq[K / 2] - 1) / 2);

So the above loop is simply trying to find all the possible pairs with remainders p and K-p for p in [0, K-1]

Upvotes: 4

Related Questions