{"id":26101,"date":"2017-10-26T19:50:04","date_gmt":"2017-10-26T14:20:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26101"},"modified":"2017-10-26T19:50:04","modified_gmt":"2017-10-26T14:20:04","slug":"c-programming-count-possible-groups","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-count-possible-groups\/","title":{"rendered":"C Programming &#8211; Count all possible groups"},"content":{"rendered":"<p>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<p>Input: arr[] = {3, 6, 7, 2, 9}<br \/>\nOutput: 8<br \/>\n\/\/ Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},<br \/>\n\/\/ {3,7,2}, {7,2,6}, {7,2,9}<br \/>\nInput: arr[] = {2, 1, 3, 4}<br \/>\nOutput: 4<br \/>\n\/\/ Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>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<p>1. Hash all elements in a count array based on remainder, i.e,<br \/>\nfor all elements a[i], do c[a[i]%3]++;<br \/>\n2. Now c[0] contains the number of elements which when divided<br \/>\nby 3 leave remainder 0 and similarly c[1] for remainder 1<br \/>\nand c[2] for 2.<br \/>\n3. Now for group of 2, we have 2 possibilities<br \/>\na. 2 elements of remainder 0 group. Such possibilities are<br \/>\nc[0]*(c[0]-1)\/2<br \/>\nb. 1 element of remainder 1 and 1 from remainder 2 group<br \/>\nSuch groups are c[1]*c[2].<br \/>\n4. Now for group of 3,we have 4 possibilities<br \/>\na. 3 elements from remainder group 0.<br \/>\nNo. of such groups are c[0]C3<br \/>\nb. 3 elements from remainder group 1.<br \/>\nNo. of such groups are c[1]C3<br \/>\nc. 3 elements from remainder group 2.<br \/>\nNo. of such groups are c[2]C3<br \/>\nd. 1 element from each of 3 groups.<br \/>\nNo. of such groups are c[0]*c[1]*c[2].<br \/>\n5. Add all the groups in steps 3 and 4 to obtain the result.<\/p>\n<div class=\"code-embed-wrapper\"> <div class=\"code-embed-infos\"> <span class=\"code-embed-name\">C Program<\/span> <\/div> <pre class=\"language-c code-embed-pre line-numbers\"  data-start=\"1\" data-line-offset=\"0\"><code class=\"language-c code-embed-code\">#include&lt;stdio.h&gt;<br\/> <br\/>\/\/ Returns count of all possible groups that can be formed from elements<br\/>\/\/ of a[].<br\/>int findgroups(int arr[], int n)<br\/>{<br\/>    \/\/ Create an array C[3] to store counts of elements with remainder<br\/>    \/\/ 0, 1 and 2.  c[i] would store count of elements with remainder i<br\/>    int c[3] = {0}, i;<br\/> <br\/>    int res = 0; \/\/ To store the result<br\/> <br\/>    \/\/ Count elements with remainder 0, 1 and 2<br\/>    for (i=0; i&lt;n; i++)<br\/>        c[arr[i]%3]++;<br\/> <br\/>    \/\/ Case 3.a: Count groups of size 2 from 0 remainder elements<br\/>    res += ((c[0]*(c[0]-1))&gt;&gt;1);<br\/> <br\/>    \/\/ Case 3.b: Count groups of size 2 with one element with 1<br\/>    \/\/ remainder and other with 2 remainder<br\/>    res += c[1] * c[2];<br\/> <br\/>    \/\/ Case 4.a: Count groups of size 3 with all 0 remainder elements<br\/>    res += (c[0] * (c[0]-1) * (c[0]-2))\/6;<br\/> <br\/>    \/\/ Case 4.b: Count groups of size 3 with all 1 remainder elements<br\/>    res += (c[1] * (c[1]-1) * (c[1]-2))\/6;<br\/> <br\/>    \/\/ Case 4.c: Count groups of size 3 with all 2 remainder elements<br\/>    res += ((c[2]*(c[2]-1)*(c[2]-2))\/6);<br\/> <br\/>    \/\/ Case 4.c: Count groups of size 3 with different remainders<br\/>    res += c[0]*c[1]*c[2];<br\/> <br\/>    \/\/ Return total count stored in res<br\/>    return res;<br\/>}<br\/> <br\/>\/\/ Driver program to test above functions<br\/>int main()<br\/>{<br\/>    int arr[] = {3, 6, 7, 2, 9};<br\/>    int n = sizeof(arr)\/sizeof(arr[0]);<br\/>    printf(&quot;Required number of groups are %d\\n&quot;, findgroups(arr,n));<br\/>    return 0;<br\/>}<\/code><\/pre> <\/div>\n<p>Output:<\/p>\n<pre>Required number of groups are 8<\/pre>\n<p>Time Complexity: O(n)<br \/>\nAuxiliary Space: O(1)<\/p>\n[ad type=&#8221;banner&#8221;]\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>C Programming &#8211; Count all possible groups &#8211; Mathematical Algorithms &#8211; 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}]}}