How to count pairs (a[i], a[j]), i < j and a[i] a[j] can be divided by k without remainder-CodePudding

I wander if it is possible to solve the problem in less than O(N^2). There is array a of length N and divisor k. Need to count all possible pairs (a[i], a[j]) such as i < j and a[i] a[j] can be divided by k without remainder. All I can get is two nested loops. I can create array with all remainders of a[i] divided by k, but then it is need to do similar nested loops through this array and it is O(N^2) again.

CodePudding user response：

Sort the array on a[i] mod k. This is done in time O(N Log N).

Scan the array with two indexes, left-to-right and right-to-left, in such a way that you detect the sequences of elements such that the sum mod k is 0, and multiply the lengths of these sequences. This is done in time O(N).

E.g. with k=5

2, 9, 21, 13, 1, 8, 22, 6

After sorting,

1, 21, 6, 22, 2, 13, 8, 9
1   1  1   2  2   3  3  4

and the sequences are

||1, 21, 6|2, 22|13, 8|9|
||1   1  1|2   2| 3  3|4|

Hence 3x1 2x2 pairs.

You need some extra trick to avoid counting the pairs i≥j. For instance, you can append to every element its initial index in the array, and sort lexicographically on the value mod k then on the index. Then when counting pairs, by a kind of merging process you can enumerate the valid pairs. The total complexity remains O(N).

2, 9, 21, 13, 1, 8, 22, 6
0  1   2   3  4  5   6  7

After sorting,

21, 1, 6, 2, 22, 13, 8, 9
 1  1  1  2   2   3  3  4
 2  4  7  0   6   3  5  1

and the sequences are

||21, 1, 6|2, 22|13, 8|9|
|| 1  1  1|2   2| 3  3|4|
|| 2  4  7|0   6| 3  5|1|

Now to count the valid pairs from |2, 22|13, 8|, we see that 2 was followed by 13, 8 and 22 was followed by nothing, hence there are 2 0 valid pairs.

CodePudding user response：

We can solve this in O(n) using a hash map where the key is the remainder and the value is the count of how many times we've seen this remainder as we iterate. For each number, after the first has been inserted, before the element, A[i], is inserted, add to the result the value at the key, k - (A[i] mod k) if it exists in the map. Then increment by 1 the count at key A[i] mod k.

CodePudding user response：

Create a bucket of remainders from 0 to k-1. Now divide every number of array with divisor k and put the number in remainder bucket based on the remainder yielded after dividing by k. Now create the pair like this -

Every number yielded remainder 1 can make pair with all numbers yielded remainder k - 1 because their sum will be perfectly divided by k (without remainder).

Similarly numbers in remainder 2 bucket will make pair with numbers in remainder k - 2 bucket. Do this for i<=j.

Also, all numbers in remainder 0 bucket will make pair among themselves.

Time complexity is O(n) and space complexity is O(k) (for bucket of remainders).

EDIT:

If just need to count the number of pairs then the remainder bucket can be like a simple array (whose all elements initialised by 0) and every element, at a particular index, will contain the number of elements of array yielded the remainder equivalent to that index. Do simple calculation - number at remainder bucket index 1 multiply by number at remainder bucket index k - 1, number at index 2 multiply by number at index k - 2 and so on (i<=j). Also, calculate the possible pairs of number at index 0. Add them all and this gives the answer.

CodePudding user response：

Write a recursive function then you will see there are oerlapping results (you are doing same calculations again). Then convet the program to a dynamic programing model which would save result for a given sub array.