Problem: Possible groups

Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three only, 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.

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:

The first line of input contains an integer T denoting the number of test cases.
The first line of each test case is N, where N is the size of array.
The second line of each test case contains N elements of input array.

Output:

Print number of all possible group.

Constraints:

1 ≤ T ≤ 50
1 ≤ N ≤ 80
1 ≤ arr[i] ≤ 100

Example:

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

Output
8
4

Implementation: Python 2.7

from itertools import *
def possible_groups(l):
    groups_2 = [x for x in list(combinations(l, 2)) if sum(x)%3==0]
    groups_3 = [x for x in list(combinations(l, 3)) if sum(x)%3==0]
    return len(groups_2) + len(groups_3)

if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        l = map(int, raw_input().split())
        print possible_groups(l)

 

Advertisements