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.

2, 9, 21, 13, 1, 8, 22, 6 with k=5

After sorting,

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

and the sequences are

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

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).

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.