0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Ananye Agarwal Feb 19 at 7:57
  • $\begingroup$ @AnanyeAgarwal: That's right. $\endgroup$ – ruakh Feb 19 at 16:33
  • $\begingroup$ 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 ? $\endgroup$ – Ananye Agarwal Feb 21 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.