Game of 3

Moderate
0/80
profile
Contributed by
0 upvote
Asked in company
Opera

Problem statement

The Ultimate Ninja Ankush was bored, so his friend Ninja Nikhil decided to give him a puzzle to keep him entertained. Nikil gave Ankush ‘N’ integers and asked how many groups of sizes 2 and 3 can be formed such that the sum of the group is divisible by 3. Although the Ultimate Ninja Ankush is brilliant, some extra help is always appreciated. Can you help The ultimate ninja Ankush with this so that he can prove to Nikhil that he, in fact, is the ultimate ninja?

More formally, Given an 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 numbers of groups that can be generated in this way.

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,3), (1,2), (1,5), (2,4), (4,5),(1,2,3), (3,4,5), (1,3,5). Therefore the final answer is 8.
Detailed explanation ( Input/output format, Notes, Images )
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’ <= 5000
0 <= ‘ARR[i]’ <= 10 ^ 4

Time Limit: 1sec.

Sample Input 1 :

2
5
1 2 3 4 5
3
3 3 3

Sample Output 1 :

8
4

Explanation of the Sample Input 1:

In the first test case, The answer will be two since eight since 8 groups can be formed, and those are (1,3), (1,2), (1,5), (2,4), (4,5),(1,2,3), (3,4,5), (1,3,5). Therefore the final answer is 8.

In the second test case, The answer will be 4, since 4 groups can be formed, and those are (3,3), (3,3), (3,3), (3,3,3). Therefore the final answer is 4.

Sample Input 2 :

2
4
2 4 6 8
5
1 3 5 7 9

Sample Output 2 :

4
7
Hint

will hashing the numbers based on their remainders with 3 help?

Approaches (1)
Storing the remainders.

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[0] * (rem[0] - 1)) / 2 to the ‘totalCount’.
    • Add (rem[1] * rem[2]) to the ‘totalCount’.
  • For adding the count of groups of 3:
    • Add (rem[0] * (rem[0] - 1) * (rem[0] - 2)) / 6 to the ‘totalCount’.
    • Add (rem[1] * (rem[1] - 1) * (rem[1] - 2)) / 6 to the ‘totalCount’.
    • Add (rem[2] * (rem[2] - 1) * (rem[2] - 2)) / 6 to the ‘totalCount’.
    • Add (rem[0] * (rem[1]) * rem[2]) to the ‘totalCount’.

Return the ‘totalCount’ as the final answer. 

Time Complexity

O(N), Where ‘N’ is the size of the array.


Since we are just looping through the array, the overall time complexity will be O(N).

Space Complexity

O(1).

 

Since we are not using any extra space, therefore the overall time complexity will be O(1). 

Code Solution
(100% EXP penalty)
Game of 3
Full screen
Console