How do I calculate the number of pairs/quadruples in an array such that their sum is divisible by '3' ?
I know the brute force approach, I am looking for a much optimized solution 🙂
I have solved the first part of the question,i.e,finding the number of pairs and it is:-
The idea is that you separate elements into buckets depending on their mod k.
For example, you have the elements: [1 3 2 6 4 5 9] and k=3 .
(number_in_array)mod 3 == 0 : [3 6 9]
(number_in_array)mod 3 == 1 : [1 4]
(number_in_array)mod 3 == 2 : [2 5]
Now, you can make pairs like so : Elements with mod 3 == 0 will match with
other elements in the mod 3 == 0 list, like so:
(3, 6) (3, 9) (6, 9)
There will be n * (n – 1) / 2 such pairs, where n is length of the list, because
the list is the same and i != j. Elements with mod 3 == 1 will match with
elements with (3 – 1) mod k = 2, so elements in the mod 3 == 2 list, like so:
(1, 2) (1, 5) (4, 2) (4, 5)
There will be n * k such elements, where n is the length of the first list, and k of the second.
Because you don't need to print the actual pairs, you need to store only the number of elements in each list.
So the answer will be = 3 + 2*2 = 7
Any ideas on how to find the quadruples?
Best Answer
The approach you describe for pairs can be directly adapted to 4-tuples. There are a few more cases, but still not too many:
Note that, just as you use ${n \choose 2} = \frac{n\left(n-1\right)}{2}$ to count the pairs from within a single bucket of $n$ elements, you can use ${n \choose 3} = \frac{n\left(n-1\right)\left(n-2\right)}{6}$ or ${n \choose 4} = \frac{n\left(n-1\right)\left(n-2\right)\left(n-3\right)}{24}$ to count the triples or quadruples, respectively, from within a single bucket of $n$ elements. (More generally, ${n \choose r} = \frac{n!}{r!\left(n-r\right)!}$.)