# Game of 3

Posted: 11 Jul, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### For example

``````Given:
‘N’ = 5, ‘ARR’ = [1, 2, 3, 4, 5].
The answer will be two since 8 since 8 pairs can be formed and those are  (1,2), (1,5), (2,4), (4,5),(1,2,3), (3,4,5), (1,3,5), (2,3,4). Therefore the final answer is 8.
``````
##### Input format:
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains a single integer, ‘N,’ where ‘N’ is the number of elements of the array.

The second line of each test case contains ‘N’ space-separated integers, denoting the array elements.
``````
##### Output Format :
``````For each test case, You are supposed to return an integer that denotes the total number of groups that can be formed.
``````
##### Note:
``````You are not required to print the expected output; it has already been taken care of. Just implement the function.
``````
##### Constraints:
``````1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
0 <= ‘ARR[i]’ <= 10 ^ 4

Time Limit: 1sec.
`````` Approach 1

The idea is to see the remainder of every element when divided by 3. A set of elements can form a group only if the sun of their remainder is multiple of 3. Therefore we can see that for making a group of 2, we will combine the number with remainder only 0 or combine numbers with remainder 1 & 2. For making a group of 3, we can take the remainder 1 & 2 & 0 or all 0 or all 2 or all 1.

The steps are as follows:

• Maintain a variable ‘totalCount’ which will store the final answer.
• Maintain an array ‘rem’ of size 3 which stores the frequency of numbers with remainders 0, 1 and 2.
• Loop through array using ‘i’:
• And do ‘rem[arr[i] % 3]++’.
• For adding the count of groups of 2:
• Add (rem * (rem - 1)) / 2 to the ‘totalCount’.
• Add (rem * rem) to the ‘totalCount’.
• For adding the count of groups of 3:
• Add (rem * (rem - 1) * (rem - 2)) / 6 to the ‘totalCount’.
• Add (rem * (rem - 1) * (rem - 2)) / 6 to the ‘totalCount’.
• Add (rem * (rem - 1) * (rem - 2)) / 6 to the ‘totalCount’.
• Add (rem * (rem) * rem) to the ‘totalCount’.
• Return the ‘totalCount’ as the final answer.