Given an unsorted integer (positive values only) array of size \u2018n\u2019, 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.<\/p>\n
Input: arr[] = {3, 6, 7, 2, 9}
\nOutput: 8
\n\/\/ Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
\n\/\/ {3,7,2}, {7,2,6}, {7,2,9}
\nInput: arr[] = {2, 1, 3, 4}
\nOutput: 4
\n\/\/ Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}<\/p>\n[ad type=\u201dbanner\u201d]\n
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.<\/p>\n
1. Hash all elements in a count array based on remainder, i.e,
\nfor all elements a[i], do c[a[i]%3]++;
\n2. Now c[0] contains the number of elements which when divided
\nby 3 leave remainder 0 and similarly c[1] for remainder 1
\nand c[2] for 2.
\n3. Now for group of 2, we have 2 possibilities
\na. 2 elements of remainder 0 group. Such possibilities are
\nc[0]*(c[0]-1)\/2
\nb. 1 element of remainder 1 and 1 from remainder 2 group
\nSuch groups are c[1]*c[2].
\n4. Now for group of 3,we have 4 possibilities
\na. 3 elements from remainder group 0.
\nNo. of such groups are c[0]C3
\nb. 3 elements from remainder group 1.
\nNo. of such groups are c[1]C3
\nc. 3 elements from remainder group 2.
\nNo. of such groups are c[2]C3
\nd. 1 element from each of 3 groups.
\nNo. of such groups are c[0]*c[1]*c[2].
\n5. Add all the groups in steps 3 and 4 to obtain the result.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Output:<\/p>\n
Required number of groups are 8<\/pre>\nTime Complexity: O(n)
\nAuxiliary Space: O(1)<\/p>\n[ad type=\u201dbanner\u201d]\n\u00a0<\/p>\n","protected":false},"excerpt":{"rendered":"
C Programming – Count all possible groups – Mathematical Algorithms – Given an unsorted integer positive values only array of size \u2018n\u2019, we can form a group <\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69866,1,74058],"tags":[73136,70860,70814,70812,70815,73138,73144,76937,73152,75061,73170,73158,76939,73394,76934,74066,76933,73145,72834,74751,76925,76936,76930,76935,76940,76929,76932,76926,73165,73395,75059,76924,76938,75689,76923,76927,73148,76931,76922,76928],"class_list":["post-26101","post","type-post","status-publish","format-standard","hentry","category-c-programming","category-coding","category-mathematical-algorithms","tag-array-c-programming-examples","tag-array-definition-in-c","tag-array-in-c","tag-array-in-c-programming","tag-array-programs-in-c","tag-array-programs-in-c-with-output","tag-c-array-programs","tag-c-language-string-functions","tag-c-program-for-array","tag-c-programming-character","tag-c-programs-on-strings","tag-c-string-functions","tag-c-string-thong","tag-compare-strings-in-c","tag-copy-string-in-c","tag-for-loop-c-programming","tag-how-to-input-a-string-in-c","tag-list-of-array-programs-in-c","tag-string-array-in-c","tag-string-compare-in-c","tag-string-data-type-in-c-language","tag-string-definition-in-c","tag-string-functions-in-c","tag-string-functions-in-c-with-examples","tag-string-functions-in-c-with-syntax-and-examples","tag-string-h-functions","tag-string-h-library-functions","tag-string-handling-functions-in-c","tag-string-hc","tag-string-in-c","tag-string-in-c-language","tag-string-manipulation-functions-in-c","tag-string-manipulation-in-c","tag-string-operations-in-c","tag-string-programming","tag-string-programming-questions","tag-string-programs-in-c","tag-string-tutorial-in-c","tag-strings-in-c","tag-write-a-program-to-accept-string-from-user"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26101"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26101\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26101"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}