# How do I calculate the number of pairs/quadruples in an array such that their sum is divisible by '3'?

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?

The approach you describe for pairs can be directly adapted to 4-tuples. There are a few more cases, but still not too many:

• all four elements ≡ 0 (mod 3)
• two elements ≡ 0 (mod 3), one element ≡ 1 (mod 3), and one element ≡ 2 (mod 3)
• one element ≡ 0 (mod 3) and three elements ≡ 1 (mod 3)
• one element ≡ 0 (mod 3) and three elements ≡ 2 (mod 3)
• two elements ≡ 1 (mod 3) and two elements ≡ 2 (mod 3)

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)!}$$.)

• I understand what you said thoroughly :-) Say, I have 10 (mod-zero-elements),11(mod-1-elements),12(mod-2-elements). Then the answer for first case is : 10 ( C ) 4 , for the second case it is :- 10 (c) 2 * 11 (c) 1* 12(c) 1 , for the third-case is : 10(c)1*11(c)3 , for the fourth case is:- 10(c)1*12 (C) 3 ,AND FOR the fifth case :- 11(c)2*12(c)2 .... Am I going right ? – Ananye Agarwal Feb 19 at 7:57
• @AnanyeAgarwal: That's right. – ruakh Feb 19 at 16:33
• I've found a very similar question to this one : - stackoverflow.com/questions/54741398/… My approach is:- make a 2d-matrix to store the powers of all the prime factors of each number, then if the all the powers in 4 distinct arrays, if we add them up and each of them is divisible by 3, then we get a perfect cube from the product of a quadruple, but its O(n^4) algorithm and too slow :( Can you suggest an algorithm with better time complexity, please ? – Ananye Agarwal Feb 21 at 5:54