LeetCodePowerofThree判断3的次方数

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?

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

这道题让我们判断一个数是不是3的次方数,在LeetCode中,有一道类似的题目Power of Two,那道题有个非常简单的方法,由于2的次方数实在太有特点,最高位为1,其他位均为0,所以特别容易,而3的次方数没有显著的特点,最直接的方法就是不停地除以3,看最后的余数是否为1,要注意考虑输入是负数和0的情况,参见代码如下:

解法一:

class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

题目中的Follow up让我们不用循环,那么有一个投机取巧的方法,由于输入是int,正数范围是0-231,在此范围中允许的最大的3的次方数为319=1162261467,那么我们只要看这个数能否被n整除即可,参见代码如下:

解法二:

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && 1162261467 % n == 0);
    }
};

最后还有一种巧妙的方法,利用对数的换底公式来做,高中学过的换底公式为logab = logcb / logca,那么如果n是3的倍数,则log3n一定是整数,我们利用换底公式可以写为log3n = log10n / log103,注意这里一定要用10为底数,不能用自然数或者2为底数,否则当n=243时会出错,原因请看这个帖子。现在问题就变成了判断log10n / log103是否为整数,在c++中判断数字a是否为整数,我们可以用 a - int(a) == 0 来判断,参见代码如下:

解法三:

class Solution {
public:
    bool isPowerOfThree(int n) {
        return (n > 0 && int(log10(n) / log10(3)) - log10(n) / log10(3) == 0);
    }
};

类似题目:

Power of Two

参考资料:

https://leetcode.com/discuss/78532/summary-all-solutions-new-method-included-at-15-30pm-jan-8th

LeetCode All in One 题目讲解汇总(持续更新中...)

更多相关文章
  • Given an integer (signed 32 bits), write a function to check whether it is a power of 4. Example:Given num = 16, return true. Given num = 5, return fa ...
  • 5.4 Explain what the following code does: ((n & (n-1)) == 0). 这道题让我们解释一个表达式((n & (n-1)) == 0),是说一个数跟比它小1的数字按位相与,结果全是0的情况,那么说明两个数每个位置上至少都有一个0,那 ...
  • 1.约定x%y为x取模y,即x除以y所得的余数,当xx^y表示x的y次方.乘方运算的优先级高于乘除和取模,加减的优先级最低. 见到x^y/z这样,就先算乘方,再算除法.A/B,称为A除以B,也称为B除A. 若A%B=0,即称为A可以被B整除,也称B可以整除A.A*B表示A乘以B或称A乘B,B乘A,B ...
  • 质数(prime number)又称素数,有无限个.一个大于1的自然数,除了1和它本身外,能被整除以其他自然数(质数),换句话说就是该数除了1和它本身以外不再有其他的因数:否则称为合数. 如何判断一个数是否是质数: 代码1: 1 /** 2 * 判断给定的数字是否为素数(质数) 3 * @param ...
  • linux学习之shell练习
    linux学习之shell练习1.描述shell程序的运行原理(可附带必要的图形说明):2.总结shell编程中所涉及到的所有知识点(如:变量.语法.命令状态等等等,要带图的哟):    总结文章:http://pizimsn.blog.51cto.com/7002551/16976713.总结课程 ...
  • C/C++语言经典.实用.趣味程序设计编程百例精解(1)1.绘制余弦曲线在屏幕上用“*”显示0~360度的余弦函数cos(x)曲线*问题分析与算法设计如果在程序中使用数组,这个问题十分简单.但若规定不能使用数组,问题就变得不容易了.关键在于余弦曲线在0~360度的区间内,一行中要显示两个点,而对一般 ...
  • Linux指令介绍 # reset -e ^B 将设定用的字串显示在萤幕上 # reset -s Erase is control-B (^B). Kill is control-U (^U). Interrupt is control-C (^C). TERM=xterm; 名称:compress ...
  • 这是我学习欧立奇<Java程序员面试宝典>第三版的笔记.这篇是基本语法部分.ClassLoader主要对类的请求提供服务,当JVM需要某类时,它根据名称向ClassLoader要求这个类,然后由ClassLoader返回这个类的class对象.在Java中,字符只以一种形式存在,那就是U ...
一周排行
  • 软件工程
        软件工程,英文名Software Engineering,是一门研究用工程化方法构 ...
  • 中国网通和中国电信两大固网运营商在今年3月才刚刚生效的一份"互不侵犯"协议,截至周末刚好度过整整100天.尽管这份协议曾因有可能导致"南北分治寡头垄断"的局面,而在消费者中引发 ...
  •     <网络工程师考试案例动手实验营> 郭春柱 编著   清华大学出版社 ISBN:9787302187868 ¥42.00元 2009年4月第2次印刷 第2章  第4章  第9章 重中之重 第10章  ...
  • 1. ACS评估简介2. ACS评估的四个组别3. 新的职业清单中ACS评估的移民职业及职业评估分析4. ACS职业评估的费用5. ACS的评估周期1. ACS评估简介 澳大利亚计算机协会(Australian Co ...
  • 环境Linux 系统:redhat as4.5Mysql 版本:mysql 4.1.22          星期一上班,就听到开发说一台mysql数据库down掉(此台数据库只做备份用).连上系统,用ps -ef | ...
  • 毕业生的商业软件开发之路第一次使用VS.NET集成开发环境
            近期开始接触到在校学生.高校实习生和毕业生,在此说一下笔者对这些徘徊在职场 ...
  • 工作中遇到linux服务器突然启动不起来了,进入grub发现没有了grub.conf和menu.lst文件,自己重新创建了也还是不行,后来就进boot下看发现原来boot下只有一个grub的文件夹,其他文件全都没有, ...
  • 下面这段代码演示了查找一个目录下所有文件的过程,将文件名存放在result.txt文件中./////////////////////////////////////////////////////////////// ...
  • 所有硬盘都分一个区,而且分区大小是2T.# parted> help mklabel> mklabel gpt> mkpart primary ext3 0 100%> select /dev ...
  • 0.引 在 windows 下安装 git 之后, git 默认的HOME和~路径一般都是C:\Users\用户名,每次得用命令切换到常用的Repository下,此操作重复而没有意义.为了修改默认路径,有两种方法: ...