我们想到的第一个解决方案是我们在学校学到的。如果一个数字的数字之和是3的倍数，那么这个数字就是3的倍数。例如，对于612，数字之和是9，所以它是3的倍数。但这种解决方案并不有效。你必须一个接一个地得到所有的十进制数字，把它们相加，然后检查总和是否是3的倍数。
null
数字的二进制表示中有一种模式，可以用来确定数字是否是3的倍数。如果奇数设置位（奇数位置设置的位）和偶数设置位的计数之差是3的倍数，则为数字。 例子： 23 (00..10111) 1） 获取奇数位置的所有设置位的计数（对于23，它是3）。 2） 获取偶数位置的所有设置位的计数（对于23，它是1）。 3） 若上述两个计数之差是3的倍数，则该数字也是3的倍数。 （对于23，它是2，所以23不是3的倍数） 再举一些例子，比如21、15等等…
Algorithm: isMutlipleOf3(n)1) Make n positive if n is negative.2) If number is 0 then return 13) If number is 1 then return 04) Initialize: odd_count = 0, even_count = 05) Loop while n != 0 a) If rightmost bit is set then increment odd count. b) Right-shift n by 1 bit c) If rightmost bit is set then increment even count. d) Right-shift n by 1 bit6) return isMutlipleOf3(odd_count - even_count)
证据： 以十进制数字中的11为例，可以证明上述观点。（在此上下文中，十进制数中的11与二进制数中的3相同） 如果奇数和偶数之和的差是11的倍数，则十进制数是11的倍数。让我们看看如何。 让我们以十进制的两位数为例 AB=11A-A+B=11A+（B-A） 所以如果（B–A）是11的倍数，那么就是AB。 让我们用三位数。 ABC=99A+A+11B-B+C=（99A+11B）+（A+C-B） 所以如果（A+C–B）是11的倍数，那么是（ABC） 现在让我们看4位数字。 ABCD=1001A+D+11C-C+999B+B-A =（1001A-999B+11C）+（D+B-A-C） 所以，如果（B+D–A–C）是11的倍数，那么是ABCD。 所有十进制数都可以继续。 上述概念可以用同样的方法证明为3的二进制数。 时间复杂性： O（logn） 节目：
C++
// CPP program to check if n is a multiple of 3 #include <bits/stdc++.h> using namespace std; /* Function to check if n is a multiple of 3*/ int isMultipleOf3( int n) { int odd_count = 0; int even_count = 0; /* Make no positive if +n is multiple of 3 then is -n. We are doing this to avoid stack overflow in recursion*/ if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; while (n) { /* If odd bit is set then increment odd counter */ if (n & 1) odd_count++; /* If even bit is set then increment even counter */ if (n & 2) even_count++; n = n >> 2; } return isMultipleOf3( abs (odd_count - even_count)); } /* Program to test function isMultipleOf3 */ int main() { int num = 24; if (isMultipleOf3(num)) printf ( "%d is multiple of 3" , num); else printf ( "%d is not a multiple of 3" , num); return 0; } |
JAVA
// Java program to check if // n is a multiple of 3 import java.lang.*; import java.util.*; class GFG { // Function to check if n // is a multiple of 3 static int isMultipleOf3( int n) { int odd_count = 0 ; int even_count = 0 ; /* Make no positive if +n is multiple of 3 then is -n. We are doing this to avoid stack overflow in recursion*/ if (n < 0 ) n = -n; if (n == 0 ) return 1 ; if (n == 1 ) return 0 ; while (n != 0 ) { /* If odd bit is set then increment odd counter */ if ((n & 1 ) != 0 ) odd_count++; /* If even bit is set then increment even counter */ if ((n & 2 ) != 0 ) even_count++; n = n >> 2 ; } return isMultipleOf3(Math.abs(odd_count - even_count)); } /* Program to test function isMultipleOf3 */ public static void main(String[] args) { int num = 24 ; if (isMultipleOf3(num) != 0 ) System.out.println(num + " is multiple of 3" ); else System.out.println(num + " is not a multiple of 3" ); } } // This code is contributed by Sahil_Bansall |
蟒蛇3
# Python program to check if n is a multiple of 3 # Function to check if n is a multiple of 3 def isMultipleOf3(n): odd_count = 0 even_count = 0 # Make no positive if + n is multiple of 3 # then is -n. We are doing this to avoid # stack overflow in recursion if (n < 0 ): n = - n if (n = = 0 ): return 1 if (n = = 1 ): return 0 while (n): # If odd bit is set then # increment odd counter if (n & 1 ): odd_count + = 1 # If even bit is set then # increment even counter if (n & 2 ): even_count + = 1 n = n >> 2 return isMultipleOf3( abs (odd_count - even_count)) # Program to test function isMultipleOf3 num = 24 if (isMultipleOf3(num)): print (num, 'is multiple of 3' ) else : print (num, 'is not a multiple of 3' ) # This code is contributed by Danish Raza |
C#
// C# program to check if // n is a multiple of 3 using System; class GFG { // Function to check if n // is a multiple of 3 static int isMultipleOf3( int n) { int odd_count = 0, even_count = 0; /* Make no positive if +n is multiple of 3 then is -n. We are doing this to avoid stack overflow in recursion*/ if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; while (n != 0) { /* If odd bit is set then increment odd counter */ if ((n & 1) != 0) odd_count++; /* If even bit is set then increment even counter */ if ((n & 2) != 0) even_count++; n = n >> 2; } return isMultipleOf3(Math.Abs(odd_count - even_count)); } // Driver Code public static void Main() { int num = 24; if (isMultipleOf3(num) != 0) Console.Write(num + " is multiple of 3" ); else Console.Write(num + " is not a multiple of 3" ); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to check if n // is a multiple of 3 // Function to check if n // is a multiple of 3 function isMultipleOf3( $n ) { $odd_count = 0; $even_count = 0; // Make no positive if +n // is multiple of 3 then is -n. // We are doing this to avoid // stack overflow in recursion if ( $n < 0) $n = - $n ; if ( $n == 0) return 1; if ( $n == 1) return 0; while ( $n ) { // If odd bit is set then // increment odd counter if ( $n & 1) $odd_count ++; // If even bit is set then // increment even counter if ( $n & 2) $even_count ++; $n = $n >> 2; } return isMultipleOf3( abs ( $odd_count - $even_count )); } // Driver Code $num = 24; if (isMultipleOf3( $num )) echo $num , "is multiple of 3" ; else echo $num , "is not a multiple of 3" ; // This code is contributed by vt_m. ?> |
Javascript
<script> /*Function to check if n is a multiple of 3*/ function isMultipleof3(n) { odd_count = 0; even_count = 0; /* Make no positive if +n is multiple of 3 then is -n. We are doing this to avoid stack overflowin recursion*/ if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; while (n) { /*If odd bit is set then increment odd counter*/ if (n & 1) odd_count++; /*If even bit is set then increment even counter*/ if (n & 2) even_count++; n = n>>2; } return isMultipleof3(Math.abs(odd_count-even_count)); } /*Program to test function isMultipleof3*/ num = 24; if (isMultipleof3(num)) document.write(num + " is multiple of 3" ); else document.write(num + " is not a multiple of 3" ); // This code is contributed by simranarora5sos </script> |
输出
24 is multiple of 3
有效方法：
使用动态编程 （自上而下的方法使用备忘录）
C++
// CPP program to check if n is a multiple of 3 #include <bits/stdc++.h> using namespace std; int static dp[1001]; /* Function to check if n is a multiple of 3*/ int isMultipleOf3( int n) { int odd_count = 0; int even_count = 0; // Base Cases if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; // If a value is already present // in dp, return it if (dp[n] != -1) return dp[n]; while (n) { /* If odd bit is set then increment odd counter */ if (n & 1) odd_count++; /* If even bit is set then increment even counter */ if (n & 2) even_count++; n = n >> 2; } dp[n] = isMultipleOf3( abs (odd_count - even_count)); // return dp return dp[n]; } /* Program to test function isMultipleOf3 */ int main() { int num = 24; memset (dp, -1, sizeof (dp)); if (isMultipleOf3(num)) printf ( "%d is multiple of 3" , num); else printf ( "%d is not a multiple of 3" , num); return 0; } |
JAVA
// JAVA program to check if n is a multiple of 3 import java.util.*; class GFG{ static int []dp ; /* Function to check if n is a multiple of 3*/ static int isMultipleOf3( int n) { int odd_count = 0 ; int even_count = 0 ; // Base Cases if (n < 0 ) n = -n; if (n == 0 ) return 1 ; if (n == 1 ) return 0 ; // If a value is already present // in dp, return it if (dp[n] != - 1 ) return dp[n]; while (n > 0 ) { /* If odd bit is set then increment odd counter */ if ((n & 1 ) != 0 ) odd_count++; /* If even bit is set then increment even counter */ if ((n & 2 ) != 0 ) even_count++; n = n >> 2 ; } dp[n] = isMultipleOf3(Math.abs(odd_count - even_count)); // return dp return dp[n]; } /* Program to test function isMultipleOf3 */ public static void main(String[] args) { int num = 24 ; dp = new int [ 1001 ]; Arrays.fill(dp, - 1 ); if (isMultipleOf3(num) == 1 ) System.out.printf( "%d is multiple of 3" , num); else System.out.printf( "%d is not a multiple of 3" , num); } } // This codeiscontributed by Rajput-Ji |
蟒蛇3
# Python program to check if n is a multiple of 3 dp = [ - 1 for i in range ( 1001 )]; ''' Function to check if n is a multiple of 3 ''' def isMultipleOf3(n): odd_count = 0 ; even_count = 0 ; # Base Cases if (n < 0 ): n = - n; if (n = = 0 ): return 1 ; if (n = = 1 ): return 0 ; # If a value is already present # in dp, return it if (dp[n] ! = - 1 ): return dp[n]; while (n > 0 ): ''' * If odd bit is set then increment odd counter ''' if ((n & 1 ) ! = 0 ): odd_count + = 1 ; ''' * If even bit is set then increment even counter ''' if ((n & 2 ) ! = 0 ): even_count + = 1 ; n = n >> 2 ; dp[n] = isMultipleOf3( abs (odd_count - even_count)); # return dp return dp[n]; ''' Program to test function isMultipleOf3 ''' if __name__ = = '__main__' : num = 24 ; if (isMultipleOf3(num) = = 1 ): print (num, "is multiple of 3" ); else : print (num, " is not a multiple of 3" ); # This code is contributed by Rajput-Ji |
C#
// C# program to check if // n is a multiple of 3 using System; class GFG { static int []dp = new int [1001]; /* Function to check if n is a multiple of 3*/ static int isMultipleOf3( int n) { int odd_count = 0; int even_count = 0; // Base Cases if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; // If a value is already present // in dp, return it if (dp[n] != -1) return dp[n]; while (n > 0) { /* If odd bit is set then increment odd counter */ if ((n & 1) != 0) odd_count++; /* If even bit is set then increment even counter */ if ((n & 2) != 0) even_count++; n = n >> 2; } dp[n] = isMultipleOf3(Math.Abs(odd_count - even_count)); // return dp return dp[n]; } // Driver Code public static void Main() { int num = 24; for ( int i = 0; i < 1001; i++) { dp[i] = -1; } if (isMultipleOf3(num) == 1) Console.Write(num + " is multiple of 3" ); else Console.Write(num + " is not a multiple of 3" ); } } // This code is contributed by Samim Hossain Mondal. |
Javascript
<script> // JavaScript program to check if n is a multiple of 3 let dp = []; for (let i = 0; i < 1001; i++) { dp[i] = -1; } /* Function to check if n is a multiple of 3*/ function isMultipleOf3(n) { let odd_count = 0; let even_count = 0; // Base Cases if (n < 0) n = -n; if (n == 0) return 1; if (n == 1) return 0; // If a value is already present // in dp, return it if (dp[n] != -1) return dp[n]; while (n) { /* If odd bit is set then increment odd counter */ if (n & 1) odd_count++; /* If even bit is set then increment even counter */ if (n & 2) even_count++; n = n >> 2; } dp[n] = isMultipleOf3(Math.abs(odd_count - even_count)); // return dp return dp[n]; } /* Program to test function isMultipleOf3 */ let num = 24; if (isMultipleOf3(num)) document.write(num + " is multiple of 3" ); else document.write(num + " is not a multiple of 3" ); // This code is contributed by Samim Hossain Mondal. </script> |
输出
24 is multiple of 3
时间复杂性： O（n）
辅助空间： O（n）
相关文章： 检查二进制流中的可除性 基于DFA的部门 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
