[leetcode]: 326. Power of Three

一时失言乱红尘 2022-06-15 01:56 285阅读 0赞

1.题目

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

给一个整数，判断是否为3的幂。不用迭代和递归，如何实现。

2.分析

一开始我走错了方向，以为3的n次方有什么规律。实际上，确实有，但通过这一规律并不是充分条件，只是必要条件。
3的n次方满足：尾数为3,9,7,1。
后来还是看了solution，大致分为两种解法：
1）求解log3(n),结果是整数则n为3的幂
2）找出32位int表示范围内的最大的3的幂1162261467。所有int范围内的3的幂都能整除1162261467。

3.代码

求log3(n)=log(n)/log(3)

  1. bool isPowerOfThree(int n) {
  2.     return fmod(log10(n) / log10(3), 1) == 0;
  3. }

所有int范围内的3的幂都能整除1162261467

  1. bool isPowerOfThree(int n) {
  2.     int max_pow = 1162261467;
  3.     if (n <= 0 || n > max_pow)
  4.         return false;
  5.     return max_pow%n == 0;
  6.     }

发表评论

表情：
评论列表 （有 0 条评论，285人围观）

还没有评论，来说两句吧...

相关阅读