# Count all possible groups of size 2 or 3 that have sum as multiple of 3

Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.
Examples:

```Input: arr[] = {3, 6, 7, 2, 9}
Output: 8
// Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
//            {3,7,2}, {7,2,6}, {7,2,9}

Input: arr[] = {2, 1, 3, 4}
Output: 4
// Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}
```

The idea is to see remainder of every element when divided by 3. A set of elements can form a group only if sun of their remainders is multiple of 3.
For example : 8, 4, 12. Now, the remainders are 2, 1, and 0 respectively. This means 8 is 2 distance away from 3s multiple (6), 4 is 1 distance away from 3s multiple(3), and 12 is 0 distance away. So, we can write the sum as 8 (can be written as 6+2), 4 (can be written as 3+1), and 12 (can be written as 12+0). Now the sum of 8, 4 and 12 can be written as 6+2+3+1+12+0. Now, 6+3+12 will always be divisible by 3 as all the terms are multiple of three. Now, we only need to check if 2+1+0 (remainders) is divisible by 3 or not which makes the complete sum divisible by 3.
Since the task is to enumerate groups, we count all elements with different remainders.

```1. Hash all elements in a count array based on remainder, i.e,
for all elements a[i], do c[a[i]%3]++;
2. Now c contains the number of elements which when divided
by 3 leave remainder 0 and similarly c for remainder 1
and c for 2.
3. Now for group of 2, we have 2 possibilities
a. 2 elements of remainder 0 group. Such possibilities are
c*(c-1)/2
b. 1 element of remainder 1 and 1 from remainder 2 group
Such groups are c*c.
4. Now for group of 3,we have 4 possibilities
a. 3 elements from remainder group 0.
No. of such groups are cC3
b. 3 elements from remainder group 1.
No. of such groups are cC3
c. 3 elements from remainder group 2.
No. of such groups are cC3
d. 1 element from each of 3 groups.
No. of such groups are c*c*c.
5. Add all the groups in steps 3 and 4 to obtain the result.
```

## C++

 `// C++ Program to count all possible  ` `// groups of size 2 or 3 that have ` `// sum as multiple of 3 ` ` `  `#include ` `using` `namespace` `std; ` ` `  `// Returns count of all possible groups  ` `// that can be formed from elements of a[]. ` `int` `findgroups(``int` `arr[], ``int` `n) ` `{ ` `    ``// Create an array C to store counts  ` `    ``// of elements with remainder 0, 1 and 2. ` `    ``// c[i] would store count of elements  ` `    ``// with remainder i ` `    ``int` `c = {0}, i; ` ` `  `    ``int` `res = 0; ``// To store the result ` ` `  `    ``// Count elements with remainder 0, 1 and 2 ` `    ``for` `(i=0; i>1); ` ` `  `    ``// Case 3.b: Count groups of size 2 with  ` `    ``// one element with 1 remainder and other ` `    ``// with 2 remainder ` `    ``res += c * c; ` ` `  `    ``// Case 4.a: Count groups of size 3 ` `    ``// with all 0 remainder elements ` `    ``res += (c * (c-1) * (c-2))/6; ` ` `  `    ``// Case 4.b: Count groups of size 3  ` `    ``// with all 1 remainder elements ` `    ``res += (c * (c-1) * (c-2))/6; ` ` `  `    ``// Case 4.c: Count groups of size 3  ` `    ``// with all 2 remainder elements ` `    ``res += ((c*(c-1)*(c-2))/6); ` ` `  `    ``// Case 4.c: Count groups of size 3 ` `    ``// with different remainders ` `    ``res += c*c*c; ` ` `  `    ``// Return total count stored in res ` `    ``return` `res; ` `} ` ` `  `// Driver Code ` `int` `main() ` `{ ` `    ``int` `arr[] = {3, 6, 7, 2, 9}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``cout << ``"Required number of groups are "`  `         ``<< findgroups(arr,n) << endl; ` `    ``return` `0; ` `} ` ` `  `// This code is contributed  ` `// by Akanksha Rai `

## C

 `// C Program to count all possible  ` `// groups of size 2 or 3 that have ` `// sum as multiple of 3 ` ` `  `#include ` ` `  `// Returns count of all possible groups that can be formed from elements ` `// of a[]. ` `int` `findgroups(``int` `arr[], ``int` `n) ` `{ ` `    ``// Create an array C to store counts of elements with remainder ` `    ``// 0, 1 and 2.  c[i] would store count of elements with remainder i ` `    ``int` `c = {0}, i; ` ` `  `    ``int` `res = 0; ``// To store the result ` ` `  `    ``// Count elements with remainder 0, 1 and 2 ` `    ``for` `(i=0; i>1); ` ` `  `    ``// Case 3.b: Count groups of size 2 with one element with 1 ` `    ``// remainder and other with 2 remainder ` `    ``res += c * c; ` ` `  `    ``// Case 4.a: Count groups of size 3 with all 0 remainder elements ` `    ``res += (c * (c-1) * (c-2))/6; ` ` `  `    ``// Case 4.b: Count groups of size 3 with all 1 remainder elements ` `    ``res += (c * (c-1) * (c-2))/6; ` ` `  `    ``// Case 4.c: Count groups of size 3 with all 2 remainder elements ` `    ``res += ((c*(c-1)*(c-2))/6); ` ` `  `    ``// Case 4.c: Count groups of size 3 with different remainders ` `    ``res += c*c*c; ` ` `  `    ``// Return total count stored in res ` `    ``return` `res; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``int` `arr[] = {3, 6, 7, 2, 9}; ` `    ``int` `n = ``sizeof``(arr)/``sizeof``(arr); ` `    ``printf``(````"Required number of groups are %d "````, findgroups(arr,n)); ` `    ``return` `0; ` `}`

## Java

 `// Java Program to count all possible  ` `// groups of size 2 or 3 that have ` `// sum as multiple of 3 ` `class` `FindGroups  ` `{ ` `    ``// Returns count of all possible groups that can be formed from elements ` `    ``// of a[]. ` ` `  `    ``int` `findgroups(``int` `arr[], ``int` `n)  ` `    ``{ ` `        ``// Create an array C to store counts of elements with remainder ` `        ``// 0, 1 and 2.  c[i] would store count of elements with remainder i ` `        ``int` `c[] = ``new` `int``[]{``0``, ``0``, ``0``}; ` `        ``int` `i; ` ` `  `        ``int` `res = ``0``; ``// To store the result ` ` `  `        ``// Count elements with remainder 0, 1 and 2 ` `        ``for` `(i = ``0``; i < n; i++) ` `            ``c[arr[i] % ``3``]++; ` ` `  `        ``// Case 3.a: Count groups of size 2 from 0 remainder elements ` `        ``res += ((c[``0``] * (c[``0``] - ``1``)) >> ``1``); ` ` `  `        ``// Case 3.b: Count groups of size 2 with one element with 1 ` `        ``// remainder and other with 2 remainder ` `        ``res += c[``1``] * c[``2``]; ` ` `  `        ``// Case 4.a: Count groups of size 3 with all 0 remainder elements ` `        ``res += (c[``0``] * (c[``0``] - ``1``) * (c[``0``] - ``2``)) / ``6``; ` ` `  `        ``// Case 4.b: Count groups of size 3 with all 1 remainder elements ` `        ``res += (c[``1``] * (c[``1``] - ``1``) * (c[``1``] - ``2``)) / ``6``; ` ` `  `        ``// Case 4.c: Count groups of size 3 with all 2 remainder elements ` `        ``res += ((c[``2``] * (c[``2``] - ``1``) * (c[``2``] - ``2``)) / ``6``); ` ` `  `        ``// Case 4.c: Count groups of size 3 with different remainders ` `        ``res += c[``0``] * c[``1``] * c[``2``]; ` ` `  `        ``// Return total count stored in res ` `        ``return` `res; ` `    ``} ` ` `  `    ``public` `static` `void` `main(String[] args)  ` `    ``{ ` `        ``FindGroups groups = ``new` `FindGroups(); ` `        ``int` `arr[] = {``3``, ``6``, ``7``, ``2``, ``9``}; ` `        ``int` `n = arr.length; ` `        ``System.out.println(``"Required number of groups are "` `                ``+ groups.findgroups(arr, n)); ` `    ``} ` `} `

## Python3

 `# Python3 Program to Count groups ` `# of size 2 or 3 that have sum ` `# as multiple of 3 ` ` `  `# Returns count of all possible ` `# groups that can be formed ` `# from elements of a[]. ` `def` `findgroups(arr, n): ` ` `  `    ``# Create an array C to store ` `    ``# counts of elements with  ` `    ``# remainder 0, 1 and 2. c[i]  ` `    ``# would store count of elements  ` `    ``# with remainder i ` `    ``c ``=` `[``0``, ``0``, ``0``] ` ` `  `    ``# To store the result ` `    ``res ``=` `0`  ` `  `    ``# Count elements with remainder  ` `    ``# 0, 1 and 2 ` `    ``for` `i ``in` `range``(``0``, n): ` `        ``c[arr[i] ``%` `3``] ``+``=` `1` ` `  `    ``# Case 3.a: Count groups of size ` `    ``# 2 from 0 remainder elements ` `    ``res ``+``=` `((c[``0``] ``*` `(c[``0``] ``-` `1``)) >> ``1``) ` ` `  `    ``# Case 3.b: Count groups of size ` `    ``# 2 with one element with 1 ` `    ``# remainder and other with 2 remainder ` `    ``res ``+``=` `c[``1``] ``*` `c[``2``] ` ` `  `    ``# Case 4.a: Count groups of size ` `    ``# 3 with all 0 remainder elements ` `    ``res ``+``=` `(c[``0``] ``*` `(c[``0``] ``-` `1``) ``*` `(c[``0``] ``-` `2``)) ``/` `6` ` `  `    ``# Case 4.b: Count groups of size 3 ` `    ``# with all 1 remainder elements ` `    ``res ``+``=` `(c[``1``] ``*` `(c[``1``] ``-` `1``) ``*` `(c[``1``] ``-` `2``)) ``/` `6` ` `  `    ``# Case 4.c: Count groups of size 3  ` `    ``# with all 2 remainder elements ` `    ``res ``+``=` `((c[``2``] ``*` `(c[``2``] ``-` `1``) ``*` `(c[``2``] ``-` `2``)) ``/` `6``) ` ` `  `    ``# Case 4.c: Count groups of size 3 ` `    ``# with different remainders ` `    ``res ``+``=` `c[``0``] ``*` `c[``1``] ``*` `c[``2``] ` ` `  `    ``# Return total count stored in res ` `    ``return` `res ` ` `  `# Driver program ` `arr ``=` `[``3``, ``6``, ``7``, ``2``, ``9``] ` `n ``=` `len``(arr) ` ` `  `print` `(``"Required number of groups are"``, ` `               ``int``(findgroups(arr, n))) ` ` `  `# This article is contributed by shreyanshi_arun `

## C#

 `// C# Program to count all possible  ` `// groups of size 2 or 3 that have ` `// sum as multiple of 3 ` `using` `System; ` ` `  `class` `FindGroups  ` `{ ` `     `  `    ``// Returns count of all possible ` `    ``// groups that can be formed  ` `    ``// from elements of a[]. ` ` `  `    ``int` `findgroups(``int` `[]arr, ``int` `n)  ` `    ``{ ` `         `  `        ``// Create an array C to store ` `        ``// counts of elements with remainder ` `        ``// 0, 1 and 2. c[i] would store  ` `        ``// count of elements with remainder i ` `        ``int` `[] c= ``new` `int``[]{0, 0, 0}; ` `        ``int` `i; ` ` `  `        ``// To store the result ` `        ``int` `res = 0; ` ` `  `        ``// Count elements with ` `        ``// remainder 0, 1 and 2 ` `        ``for` `(i = 0; i < n; i++) ` `            ``c[arr[i] % 3]++; ` ` `  `        ``// Case 3.a: Count groups of size ` `        ``// 2 from 0 remainder elements ` `        ``res += ((c * (c - 1)) >> 1); ` ` `  `        ``// Case 3.b: Count groups of size 2 ` `        ``// with one element with 1 remainder ` `        ``// and other with 2 remainder ` `        ``res += c * c; ` ` `  `        ``// Case 4.a: Count groups of size 3  ` `        ``// with all 0 remainder elements ` `        ``res += (c * (c - 1) * ` `               ``(c - 2)) / 6; ` ` `  `        ``// Case 4.b: Count groups of size 3  ` `        ``// with all 1 remainder elements ` `        ``res += (c * (c - 1) *  ` `               ``(c - 2)) / 6; ` ` `  `        ``// Case 4.c: Count groups of size 3  ` `        ``// with all 2 remainder elements ` `        ``res += ((c * (c - 1) *  ` `                ``(c - 2)) / 6); ` ` `  `        ``// Case 4.c: Count groups of size 3 ` `        ``// with different remainders ` `        ``res += c * c * c; ` ` `  `        ``// Return total count stored in res ` `        ``return` `res; ` `    ``} ` ` `  `    ``// Driver Code ` `    ``public` `static` `void` `Main()  ` `    ``{ ` `        ``FindGroups groups = ``new` `FindGroups(); ` `        ``int` `[]arr = {3, 6, 7, 2, 9}; ` `        ``int` `n = arr.Length; ` `        ``Console.Write(``"Required number of groups are "` `                       ``+ groups.findgroups(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by nitin mittal. `

/div>

## PHP

 `> 1); ` ` `  `    ``// Case 3.b: Count groups of size ` `    ``// 2 with one element with 1 ` `    ``// remainder and other with 2 remainder ` `    ``\$res` `+= ``\$c`` * ``\$c``; ` ` `  `    ``// Case 4.a: Count groups of size ` `    ``// 3 with all 0 remainder elements ` `    ``\$res` `+= (``\$c`` * (``\$c`` - 1) *  ` `            ``(``\$c`` - 2)) / 6; ` ` `  `    ``// Case 4.b: Count groups of size 3 ` `    ``// with all 1 remainder elements ` `    ``\$res` `+= (``\$c`` * (``\$c`` - 1) *  ` `            ``(``\$c`` - 2)) / 6; ` ` `  `    ``// Case 4.c: Count groups of size 3  ` `    ``// with all 2 remainder elements ` `    ``\$res` `+= ((``\$c`` * (``\$c`` - 1) *  ` `             ``(``\$c`` - 2)) / 6); ` ` `  `    ``// Case 4.c: Count groups of size 3 ` `    ``// with different remainders ` `    ``\$res` `+= ``\$c`` * ``\$c`` * ``\$c``; ` ` `  `    ``// Return total count stored in res ` `    ``return` `\$res``; ` `} ` ` `  `// Driver Code ` `\$arr` `= ``array``(3, 6, 7, 2, 9); ` `\$n` `= ``count``(``\$arr``); ` ` `  `echo` `"Required number of groups are "` `.  ` `           ``(int)(findgroups(``\$arr``, ``\$n``)); ` ` `  `// This code is contributed by mits ` `?> `

Output:

`Required number of groups are 8`

Time Complexity: O(n)
Auxiliary Space: O(1)

## tags:

Arrays Amazon Amazon Arrays