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 ...
一周排行
  • #include <iostream> using namespace std; class date { friend ostream& operator<<(ostream& ...
  • MySQL复制详解
    目录:       1.简介       2.原理       3.常见复制架构      ...
  •  Linux下随机启动程序介绍 -----------------------------------------------------------------Linux下随机启动程序必启服务1.atd 运行用户用 ...
  • 正则表达式 - 语法 正则表达式(regular expression)描述了一种字符串匹配的模式,可以用来检查一个串是否含有某种子串.将匹配的子串做替换或者从某个串中取出符合某个条件的子串等. 列目录时, dir ...
  • 详解运维监控利器Nagios 系列(三)-配置Nagios监控系统 (3)上接详解运维监控利器Nagios 系列(三)-配置Nagios监控系统 (2)http://xmshuiyong.blog.51cto.com ...
  • Android2.1开发环境搭建
    1. 安装JDK5或更高版本(如果以前没有安过的话). 2. 安装Eclipse3.4或更 ...
  • 需求:自定义apache的404错误页面,使客户看到时出现的是“正在维护中,.........”等比较人性化得信息# vi /etc/httpd/conf/httpd.conf  取消 ErrorDocument 4 ...
  • android-async-http框架之与网络进行数据交互
    (尊重劳动成果,转载请注明出处,谢谢.http://www.cnblogs.com/cle ...
  • postfix管理邮件队列邮件配置好后,会设置五个不同的用途的队列,包括输入(incoming),活动(active),等待(deferred),故障(corrupt),保留(hold),每一个队列在queue_di ...
  • Code maturity level options代码成熟度选项Prompt for development and/or incomplete code/drivers显示尚在开发中或尚未完成的代码与驱动.除非 ...