给定一个正整数，编写一个函数来确定它是否是三的幂。 例如：
null
Input : 3Output :YesInput :6Output :No
递归方法：
检查数字是否可被3整除，如果是，则继续递归检查数字/3。如果这个数字可以减少到1，那么这个数字可以被3整除，否则不能。
C++
#include <bits/stdc++.h> #define ll long long using namespace std; bool isPower_of_Three(ll n) { if (n <= 0) return false ; if (n % 3 == 0) return isPower_of_Three(n / 3); if (n == 1) return true ; return false ; } int main() { ll num1; num1 = 243; if (isPower_of_Three(num1)) cout << "Yes" << endl; else cout << "No" << endl; ll num2 = 6; if (isPower_of_Three(num2)) cout << "Yes" << endl; else cout << "No" << endl; return 0; } |
JAVA
import java.util.*; class GFG{ static boolean isPower_of_Three( long n) { if (n <= 0 ) return false ; if (n % 3 == 0 ) return isPower_of_Three(n / 3 ); if (n == 1 ) return true ; return false ; } // Driver code public static void main(String[] args) { long num1 = 243 ; if (isPower_of_Three(num1)) System.out.print( "Yes" + "" ); else System.out.print( "No" + "" ); long num2 = 6 ; if (isPower_of_Three(num2)) System.out.print( "Yes" + "" ); else System.out.print( "No" + "" ); } } // This code is contributed by umadevi9616 |
Python3
def isPower_of_Three(n): if (n < = 0 ): return False if (n % 3 = = 0 ): return isPower_of_Three(n / / 3 ) if (n = = 1 ): return True return False # Driver code num1 = 243 if (isPower_of_Three(num1)): print ( "Yes" ) else : print ( "No" ) num2 = 6 if (isPower_of_Three(num2)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by shivanisinghss2110 |
C#
using System; class GFG{ static Boolean isPower_of_Three( long n) { if (n <= 0) return false ; if (n % 3 == 0) return isPower_of_Three(n / 3); if (n == 1) return true ; return false ; } // Driver code public static void Main(String[] args) { long num1 = 243; if (isPower_of_Three(num1)) Console.Write( "Yes" + "" ); else Console.Write( "No" + "" ); long num2 = 6; if (isPower_of_Three(num2)) Console.Write( "Yes" + "" ); else Console.Write( "No" + "" ); } } // this code is contributed by shivanisinghss2110 |
Javascript
<script> function isPower_of_Three(n) { if (n <= 0) return false ; if (n % 3 == 0) return isPower_of_Three(n / 3); if (n == 1) return true ; return false ; } let num1 = 243; if (isPower_of_Three(num1)) document.write( "Yes" ); else document.write( "No" ); let num2 = 6; if (isPower_of_Three(num2)) document.write( "Yes" ); else document.write( "</br>No" ); //This code is contributed by vaibhavrabadiyaa3. </script> |
输出
YesNo
方法： 逻辑很简单。除3的幂外，任何整数除以整数可容纳的3值的最高幂3^19=1162261467（假设整数使用32位存储）将给出非零提示。
C++
// C++ program to check if a number is power // of 3 or not. #include <iostream> using namespace std; // Returns true if n is power of 3, else false bool check( int n) { if (n <= 0) return false ; /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) .*/ return 1162261467 % n == 0; } // Driver code int main() { int n = 9; if (check(n)) cout << "Yes" ; else cout << "No" ; return 0; } // This code is contributed by shivanisinghss2110 |
C
// C++ program to check if a number is power // of 3 or not. #include <stdio.h> #include <stdbool.h> // Returns true if n is power of 3, else false bool check( int n) { if (n <= 0) return false ; /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) .*/ return 1162261467 % n == 0; } // Driver code int main() { int n = 9; if (check(n)) printf ( "Yes" ); else printf ( "No" ); return 0; } |
JAVA
// Java program to check if a number is power // of 3 or not. public class Power_3 { // Returns true if n is power of 3, else false static boolean check( int n) { /* To prevent java.lang.ArithmeticException: / by zero and negative n */ if (n <= 0 ) return false ; /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) .*/ return 1162261467 % n == 0 ; } // Driver code public static void main(String args[]) { int n = 9 ; if (check(n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Sumit Ghosh |
python
# Python program to check if a number is power # of 3 or not. # Returns true if n is power of 3, else false def check(n): """ The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) .""" return 1162261467 % n = = 0 # Driver code n = 9 if (check(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Sachin Bisht |
C#
// C# program to check if a number // is power of 3 or not. using System; public class GFG { // Returns true if n is power // of 3, else false static bool check( int n) { if (n <= 0) return false ; /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) .*/ return 1162261467 % n == 0; } // Driver code public static void Main() { int n = 9; if (check(n)) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by // nitin mittal. |
PHP
<?php // PHP program to check if a // number is power of 3 or not. // Returns true if n is // power of 3, else false function check( $n ) { /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) . */ return 1162261467 % $n == 0; } // Driver code $n = 9; if (check( $n )) echo ( "Yes" ); else echo ( "No" ); // This code is contributed by nitin mittal ?> |
Javascript
<script> // Javascript program to check if a // number is power of 3 or not. // Returns true if n is // power of 3, else false function check(n) { /* The maximum power of 3 value that integer can hold is 1162261467 ( 3^19 ) . */ return 1162261467 % n == 0; } // Driver code let n = 9; if (check(n)) document.write( "Yes" ); else document.write( "No" ); // This code is contributed by nitin _saurabh_jaiswal </script> |
输出
Yes
时间复杂性： O（1）
辅助空间： O（1） 本文由 杰贝辛赫和里亚扎斯 .
方法：
该方法基于以下简单观察结果。
![图片[1]-找出给定整数是否为3的幂-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20210827/geeks_GFGPowerOfThree.PNG)
观察1 ：如果有三个数的幂，它肯定以3、9、7或1结尾。
观察2 ：如果一个数字以这四位数字中的一位结尾，我们只需要检查三的幂，这将保证一个数字以最后一位结尾。例如，如果一个给定的数字以1结尾，那么它必须是第四、第八或第十二位，依此类推，如果有的话。
既然我们对观察结果已经很清楚了，那么让我们来看看算法。
算法：
步骤1：如果给定的数字n不是以3、9、7或1结尾，则表示该数字不是三的幂，因此返回FALSE。
第2步：如果没有，我们创建一个包含4个条目的映射，以保持幂到三（1,2,3,4）和数字的最后一位（3,9,7,1）之间的映射。
第三步：从给定的数字中提取最后一个数字，并在地图中查找其对应的幂。
第4步：如果这个幂在提升到3时等于n，则返回TRUE。
第5步：如果增加到3的功率小于n，则将功率直接增加4，然后循环第4步，直到增加到3的功率大于n。
第6步：如果增加到3的功率超过给定的数字，则返回FALSE。
C++
#include <bits/stdc++.h> using namespace std; bool isPowerOfThree( int n) { if (n == 1) return true ; int lastDigit = n % 10; map< int , int > map; map[3] = 1; map[9] = 2; map[7] = 3; map[1] = 4; if (!map[lastDigit]) return false ; int power = map[lastDigit]; double powerOfThree = pow (3, power); while (powerOfThree <= n) { if (powerOfThree == n) return true ; power = power + 4; powerOfThree = pow (3, power); } return false ; } int main() { int n = 81; cout << (isPowerOfThree(n) ? "true" : "false" ) << endl; n = 91; cout << (isPowerOfThree(n) ? "true" : "false" ) << endl; return 0; } // This code is contributed by umadevi9616 |
JAVA
/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG { public static boolean isPowerOfThree( int n) { if (n == 1 ) return true ; int lastDigit = n % 10 ; Map<Integer, Integer> map = new HashMap<>(); map.put( 3 , 1 ); map.put( 9 , 2 ); map.put( 7 , 3 ); map.put( 1 , 4 ); if (map.get(lastDigit) == null ) return false ; int power = map.get(lastDigit); double powerOfThree = Math.pow( 3 , power); while (powerOfThree <= n) { if (powerOfThree == n) return true ; power = power + 4 ; powerOfThree = Math.pow( 3 , power); } return false ; } public static void main(String[] args) { int n = 81 ; System.out.println(isPowerOfThree(n)); n = 91 ; System.out.println(isPowerOfThree(n)); } } |
Python3
'''package whatever #do not write package name here ''' def isPowerOfThree(n): if (n = = 1 ): return True ; lastDigit = n % 10 ; map = [ 0 ] * 1000 ; map [ 3 ] = 1 ; map [ 9 ] = 2 ; map [ 7 ] = 3 ; map [ 1 ] = 4 ; if ( map [lastDigit] = = None ): return False ; power = map [lastDigit]; powerOfThree = pow ( 3 , power); while (powerOfThree < = n): if (powerOfThree = = n): return True ; power = power + 4 ; powerOfThree = pow ( 3 , power); return False ; if __name__ = = '__main__' : n = 81 ; print (isPowerOfThree(n)); n = 91 ; print (isPowerOfThree(n)); # This code contributed by umadevi9616 |
C#
/*package whatever //do not write package name here */ using System; using System.Collections.Generic; public class GFG { public static bool isPowerOfThree( int n) { if (n == 1) return true ; int lastDigit = n % 10; Dictionary< int , int > map = new Dictionary< int , int >(); map.Add(3, 1); map.Add(9, 2); map.Add(7, 3); map.Add(1, 4); if (!map.ContainsValue(lastDigit)) return false ; int power = map[lastDigit]; double powerOfThree = Math.Pow(3, power); while (powerOfThree <= n) { if (powerOfThree == n) return true ; power = power + 4; powerOfThree = Math.Pow(3, power); } return false ; } public static void Main(String[] args) { int n = 81; Console.WriteLine(isPowerOfThree(n)); n = 91; Console.WriteLine(isPowerOfThree(n)); } } // This code is contributed by umadevi9616 |
Javascript
<script> /*package whatever //do not write package name here */ function isPowerOfThree(n) { if (n == 1) return true ; var lastDigit = n % 10; var map = new Map(); map.set(3, 1); map.set(9, 2); map.set(7, 3); map.set(1, 4); if (map.get(lastDigit) == null ) return false ; var power = map.get(lastDigit); var powerOfThree = Math.pow(3, power); while (powerOfThree <= n) { if (powerOfThree == n) return true ; power = power + 4; powerOfThree = Math.pow(3, power); } return false ; } // Driver code var n = 81; document.write(isPowerOfThree(n)+ "<br/>" ); n = 91; document.write(isPowerOfThree(n)); // This code is contributed by umadevi9616 </script> |
输出
truefalse
分析：
运行时复杂性：
O（1）：由于给定的数字是一个整数，它的最大值可以是2147483647（32位），小于或等于该数字的三次幂的最高值为3^19=116261467。由于我们将功率增加4，我们将有一个循环最多运行5次，因此O（1）。
空间复杂性：
O（1）：因为不管数字多大，地图上只有4个条目。
这种方法是由 德格什·瓦莱查。
如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
