给定一个大小为“n”的未排序整数（仅限正值）数组，我们可以形成一个由两个或三个元素组成的组，该组中所有元素的总和应为3的倍数。计算以这种方式生成的所有可能的组数。 例如：
null
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}
我们的想法是将每个元素的余数除以3。一组元素只有在其余数的太阳是3的倍数时才能形成一个群。 例如： 8, 4, 12. 现在，余数分别是2、1和0。这意味着8表示距离3s倍数2（6），4表示距离3s倍数1（3），12表示距离0。所以，我们可以把和写成8（可以写成6+2），4（可以写成3+1），12（可以写成12+0）。现在8，4和12之和可以写成6+2+3+1+12+0。现在，6+3+12总是可以被3整除，因为所有的项都是3的倍数。现在，我们只需要检查2+1+0（余数）是否可以被3整除，这使得整和可以被3整除。 因为任务是枚举组，所以我们用不同的余数来计算所有元素。
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.
C++
// C++ Program to count all possible // groups of size 2 or 3 that have // sum as multiple of 3 #include<bits/stdc++.h> using namespace std; // Returns count of all possible groups // that can be formed from elements of a[]. int findgroups( int arr[], int n) { // Create an array C[3] to store counts // of elements with remainder 0, 1 and 2. // c[i] would store count of elements // with remainder i int c[3] = {0}, i; int res = 0; // To store the result // Count elements with remainder 0, 1 and 2 for (i=0; i<n; i++) c[arr[i]%3]++; // Case 3.a: Count groups of size 2 // from 0 remainder elements res += ((c[0]*(c[0]-1))>>1); // Case 3.b: Count groups of size 2 with // one element with 1 remainder and other // with 2 remainder res += c[1] * c[2]; // Case 4.a: Count groups of size 3 // with all 0 remainder elements res += (c[0] * (c[0]-1) * (c[0]-2))/6; // Case 4.b: Count groups of size 3 // with all 1 remainder elements res += (c[1] * (c[1]-1) * (c[1]-2))/6; // Case 4.c: Count groups of size 3 // with all 2 remainder elements res += ((c[2]*(c[2]-1)*(c[2]-2))/6); // Case 4.c: Count groups of size 3 // with different remainders res += c[0]*c[1]*c[2]; // Return total count stored in res return res; } // Driver Code int main() { int arr[] = {3, 6, 7, 2, 9}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Required number of groups are " << findgroups(arr,n) << endl; return 0; } // This code is contributed // by Akanksha Rai |
C
// C Program to count all possible // groups of size 2 or 3 that have // sum as multiple of 3 #include<stdio.h> // Returns count of all possible groups that can be formed from elements // of a[]. int findgroups( int arr[], int n) { // Create an array C[3] to store counts of elements with remainder // 0, 1 and 2. c[i] would store count of elements with remainder i int c[3] = {0}, i; int res = 0; // To store the result // Count elements with remainder 0, 1 and 2 for (i=0; i<n; i++) c[arr[i]%3]++; // Case 3.a: Count groups of size 2 from 0 remainder elements res += ((c[0]*(c[0]-1))>>1); // Case 3.b: Count groups of size 2 with one element with 1 // remainder and other with 2 remainder res += c[1] * c[2]; // Case 4.a: Count groups of size 3 with all 0 remainder elements res += (c[0] * (c[0]-1) * (c[0]-2))/6; // Case 4.b: Count groups of size 3 with all 1 remainder elements res += (c[1] * (c[1]-1) * (c[1]-2))/6; // Case 4.c: Count groups of size 3 with all 2 remainder elements res += ((c[2]*(c[2]-1)*(c[2]-2))/6); // Case 4.c: Count groups of size 3 with different remainders res += c[0]*c[1]*c[2]; // Return total count stored in res return res; } // Driver program to test above functions int main() { int arr[] = {3, 6, 7, 2, 9}; int n = sizeof (arr)/ sizeof (arr[0]); printf ( "Required number of groups are %d" , findgroups(arr,n)); return 0; } |
JAVA
// Java Program to count all possible // groups of size 2 or 3 that have // sum as multiple of 3 class FindGroups { // Returns count of all possible groups that can be formed from elements // of a[]. int findgroups( int arr[], int n) { // Create an array C[3] to store counts of elements with remainder // 0, 1 and 2. c[i] would store count of elements with remainder i int c[] = new int []{ 0 , 0 , 0 }; int i; int res = 0 ; // To store the result // Count elements with remainder 0, 1 and 2 for (i = 0 ; i < n; i++) c[arr[i] % 3 ]++; // Case 3.a: Count groups of size 2 from 0 remainder elements res += ((c[ 0 ] * (c[ 0 ] - 1 )) >> 1 ); // Case 3.b: Count groups of size 2 with one element with 1 // remainder and other with 2 remainder res += c[ 1 ] * c[ 2 ]; // Case 4.a: Count groups of size 3 with all 0 remainder elements res += (c[ 0 ] * (c[ 0 ] - 1 ) * (c[ 0 ] - 2 )) / 6 ; // Case 4.b: Count groups of size 3 with all 1 remainder elements res += (c[ 1 ] * (c[ 1 ] - 1 ) * (c[ 1 ] - 2 )) / 6 ; // Case 4.c: Count groups of size 3 with all 2 remainder elements res += ((c[ 2 ] * (c[ 2 ] - 1 ) * (c[ 2 ] - 2 )) / 6 ); // Case 4.c: Count groups of size 3 with different remainders res += c[ 0 ] * c[ 1 ] * c[ 2 ]; // Return total count stored in res return res; } public static void main(String[] args) { FindGroups groups = new FindGroups(); int arr[] = { 3 , 6 , 7 , 2 , 9 }; int n = arr.length; System.out.println( "Required number of groups are " + groups.findgroups(arr, n)); } } |
Python3
# Python3 Program to Count groups # of size 2 or 3 that have sum # as multiple of 3 # Returns count of all possible # groups that can be formed # from elements of a[]. def findgroups(arr, n): # Create an array C[3] to store # counts of elements with # remainder 0, 1 and 2. c[i] # would store count of elements # with remainder i c = [ 0 , 0 , 0 ] # To store the result res = 0 # Count elements with remainder # 0, 1 and 2 for i in range ( 0 , n): c[arr[i] % 3 ] + = 1 # Case 3.a: Count groups of size # 2 from 0 remainder elements res + = ((c[ 0 ] * (c[ 0 ] - 1 )) >> 1 ) # Case 3.b: Count groups of size # 2 with one element with 1 # remainder and other with 2 remainder res + = c[ 1 ] * c[ 2 ] # Case 4.a: Count groups of size # 3 with all 0 remainder elements res + = (c[ 0 ] * (c[ 0 ] - 1 ) * (c[ 0 ] - 2 )) / 6 # Case 4.b: Count groups of size 3 # with all 1 remainder elements res + = (c[ 1 ] * (c[ 1 ] - 1 ) * (c[ 1 ] - 2 )) / 6 # Case 4.c: Count groups of size 3 # with all 2 remainder elements res + = ((c[ 2 ] * (c[ 2 ] - 1 ) * (c[ 2 ] - 2 )) / 6 ) # Case 4.c: Count groups of size 3 # with different remainders res + = c[ 0 ] * c[ 1 ] * c[ 2 ] # Return total count stored in res return res # Driver program arr = [ 3 , 6 , 7 , 2 , 9 ] n = len (arr) print ( "Required number of groups are" , int (findgroups(arr, n))) # This article is contributed by shreyanshi_arun |
C#
// C# Program to count all possible // groups of size 2 or 3 that have // sum as multiple of 3 using System; class FindGroups { // Returns count of all possible // groups that can be formed // from elements of a[]. int findgroups( int []arr, int n) { // Create an array C[3] to store // counts of elements with remainder // 0, 1 and 2. c[i] would store // count of elements with remainder i int [] c= new int []{0, 0, 0}; int i; // To store the result int res = 0; // Count elements with // remainder 0, 1 and 2 for (i = 0; i < n; i++) c[arr[i] % 3]++; // Case 3.a: Count groups of size // 2 from 0 remainder elements res += ((c[0] * (c[0] - 1)) >> 1); // Case 3.b: Count groups of size 2 // with one element with 1 remainder // and other with 2 remainder res += c[1] * c[2]; // Case 4.a: Count groups of size 3 // with all 0 remainder elements res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6; // Case 4.b: Count groups of size 3 // with all 1 remainder elements res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6; // Case 4.c: Count groups of size 3 // with all 2 remainder elements res += ((c[2] * (c[2] - 1) * (c[2] - 2)) / 6); // Case 4.c: Count groups of size 3 // with different remainders res += c[0] * c[1] * c[2]; // Return total count stored in res return res; } // Driver Code public static void Main() { FindGroups groups = new FindGroups(); int []arr = {3, 6, 7, 2, 9}; int n = arr.Length; Console.Write( "Required number of groups are " + groups.findgroups(arr, n)); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP Program to Count groups of size // 2 or 3 that have sum as multiple of 3 // Returns count of all possible groups // that can be formed from elements of a[]. function findgroups( $arr , $n ) { // Create an array C[3] to store counts // of elements with remainder 0, 1 and 2. // c[i] would store count of elements // with remainder i $c = array (0, 0, 0); // To store the result $res = 0; // Count elements with remainder // 0, 1 and 2 for ( $i = 0; $i < $n ; $i ++) $c [ $arr [ $i ] % 3] += 1; // Case 3.a: Count groups of size // 2 from 0 remainder elements $res += (( $c [0] * ( $c [0] - 1)) >> 1); // Case 3.b: Count groups of size // 2 with one element with 1 // remainder and other with 2 remainder $res += $c [1] * $c [2]; // Case 4.a: Count groups of size // 3 with all 0 remainder elements $res += ( $c [0] * ( $c [0] - 1) * ( $c [0] - 2)) / 6; // Case 4.b: Count groups of size 3 // with all 1 remainder elements $res += ( $c [1] * ( $c [1] - 1) * ( $c [1] - 2)) / 6; // Case 4.c: Count groups of size 3 // with all 2 remainder elements $res += (( $c [2] * ( $c [2] - 1) * ( $c [2] - 2)) / 6); // Case 4.c: Count groups of size 3 // with different remainders $res += $c [0] * $c [1] * $c [2]; // Return total count stored in res return $res ; } // Driver Code $arr = array (3, 6, 7, 2, 9); $n = count ( $arr ); echo "Required number of groups are " . (int)(findgroups( $arr , $n )); // This code is contributed by mits ?> |
Javascript
<script> // JavaScript Program to count all possible // groups of size 2 or 3 that have // sum as multiple of 3 // Returns count of all possible groups // that can be formed from elements of a[]. function findgroups(arr, n){ // Create an array C[3] to store counts // of elements with remainder 0, 1 and 2. // c[i] would store count of elements // with remainder i let c = [0,0,0]; let i; // To store the result let res = 0; // Count elements with remainder 0, 1 and 2 for (i=0; i<n; i++) c[arr[i]%3]++; // Case 3.a: Count groups of size 2 // from 0 remainder elements res += ((c[0]*(c[0]-1))>>1); // Case 3.b: Count groups of size 2 with // one element with 1 remainder and other // with 2 remainder res += c[1] * c[2]; // Case 4.a: Count groups of size 3 // with all 0 remainder elements res += (c[0] * (c[0]-1) * Math.floor((c[0]-2))/6); // Case 4.b: Count groups of size 3 // with all 1 remainder elements res += (c[1] * (c[1]-1) * Math.floor((c[1]-2))/6); // Case 4.c: Count groups of size 3 // with all 2 remainder elements res += (Math.floor(c[2]*(c[2]-1)*(c[2]-2))/6); // Case 4.c: Count groups of size 3 // with different remainders res += c[0]*c[1]*c[2]; // Return total count stored in res return res; } // Driver Code let arr = [3, 6, 7, 2, 9]; let n = arr.length; document.write( "Required number of groups are " + findgroups(arr,n)); </script> |
输出：
Required number of groups are 8
时间复杂性： O（n） 辅助空间： O（1） 本文由 阿密特·贾恩 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
