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.
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}
[ad type=”banner”]
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. 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[0] contains the number of elements which when divided
by 3 leave remainder 0 and similarly c[1] for remainder 1
and c[2] for 2.
3. Now for group of 2, we have 2 possibilities
a. 2 elements of remainder 0 group. Such possibilities are
c[0]*(c[0]-1)/2
b. 1 element of remainder 1 and 1 from remainder 2 group
Such groups are c[1]*c[2].
4. Now for group of 3,we have 4 possibilities
a. 3 elements from remainder group 0.
No. of such groups are c[0]C3
b. 3 elements from remainder group 1.
No. of such groups are c[1]C3
c. 3 elements from remainder group 2.
No. of such groups are c[2]C3
d. 1 element from each of 3 groups.
No. of such groups are c[0]*c[1]*c[2].
5. Add all the groups in steps 3 and 4 to obtain the result.
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0A%2F%2F%20Returns%20count%20of%20all%20possible%20groups%20that%20can%20be%20formed%20from%20elements%0A%2F%2F%20of%20a%5B%5D.%0Aint%20findgroups(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Create%20an%20array%20C%5B3%5D%20to%20store%20counts%20of%20elements%20with%20remainder%0A%20%20%20%20%2F%2F%200%2C%201%20and%202.%20%20c%5Bi%5D%20would%20store%20count%20of%20elements%20with%20remainder%20i%0A%20%20%20%20int%20c%5B3%5D%20%3D%20%7B0%7D%2C%20i%3B%0A%20%0A%20%20%20%20int%20res%20%3D%200%3B%20%2F%2F%20To%20store%20the%20result%0A%20%0A%20%20%20%20%2F%2F%20Count%20elements%20with%20remainder%200%2C%201%20and%202%0A%20%20%20%20for%20(i%3D0%3B%20i%3Cn%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20c%5Barr%5Bi%5D%253%5D%2B%2B%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%203.a%3A%20Count%20groups%20of%20size%202%20from%200%20remainder%20elements%0A%20%20%20%20res%20%2B%3D%20((c%5B0%5D*(c%5B0%5D-1))%3E%3E1)%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%203.b%3A%20Count%20groups%20of%20size%202%20with%20one%20element%20with%201%0A%20%20%20%20%2F%2F%20remainder%20and%20other%20with%202%20remainder%0A%20%20%20%20res%20%2B%3D%20c%5B1%5D%20*%20c%5B2%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%204.a%3A%20Count%20groups%20of%20size%203%20with%20all%200%20remainder%20elements%0A%20%20%20%20res%20%2B%3D%20(c%5B0%5D%20*%20(c%5B0%5D-1)%20*%20(c%5B0%5D-2))%2F6%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%204.b%3A%20Count%20groups%20of%20size%203%20with%20all%201%20remainder%20elements%0A%20%20%20%20res%20%2B%3D%20(c%5B1%5D%20*%20(c%5B1%5D-1)%20*%20(c%5B1%5D-2))%2F6%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%204.c%3A%20Count%20groups%20of%20size%203%20with%20all%202%20remainder%20elements%0A%20%20%20%20res%20%2B%3D%20((c%5B2%5D*(c%5B2%5D-1)*(c%5B2%5D-2))%2F6)%3B%0A%20%0A%20%20%20%20%2F%2F%20Case%204.c%3A%20Count%20groups%20of%20size%203%20with%20different%20remainders%0A%20%20%20%20res%20%2B%3D%20c%5B0%5D*c%5B1%5D*c%5B2%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Return%20total%20count%20stored%20in%20res%0A%20%20%20%20return%20res%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B3%2C%206%2C%207%2C%202%2C%209%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20printf(%22Required%20number%20of%20groups%20are%20%25d%5Cn%22%2C%20findgroups(arr%2Cn))%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Program” highlight=”” provider=”manual”/]
Output:
Required number of groups are 8
Time Complexity: O(n)
Auxiliary Space: O(1)
[ad type=”banner”]