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 ...
一周排行
  • JTable的应用
    最近项目中使用到一个table表格,表格的样子如下: 可以修改数量,以及折扣,对应的最终价 ...
  • 经常遇到条件为in的模糊查询,sql传参可以在service中直接传递参数,不必使用占位符 select * from ud_order where status in ("+status+")参 ...
  • ==>MySQL 字段数据类型/长度1.数值类型列类型 需要的存储量TINYINT 1 字节SMALLINT 2 个字节MEDIUMINT 3 个字节INT 4 个字节INTEGER 4 个字节BIGINT 8 ...
  • 从一名软件开发人员转型为一名HelpDesk人员...有人说,这转型够失败的..有人说,这2个职业不相关吧......ok..你们都是对的.但是,Just Do IT.嘎嘎..从事HelpDesk有一点点地时间了.. ...
  • RedHatLinuxEnterprise5安装Oracle10G及Tomcat发布
    1. 前言希望本文能够帮助在测试环境上以最快的速度在Red Hat Linux Enter ...
  • # setup 打开Linux防火墙在Other Port里加上pop3:tcp即可打开110端口查看本机关于IPTABLES的设置情况# iptables -L -nv#屏蔽单个IP的命令是iptables -I ...
  • 场景:    CentOS6.3的二次封装版本,安装hortonworks的hadoop发行版,并按照其官方文档实现高可用,但无fence设备支持,因此导致断网和断电测试时,备用HA节点无法得到资源释放的通知.   ...
  • 我们今天的主角是AbstractRoutingDataSource,在Spring2.0.1发布之后,引入了AbstractRoutingDataSource,使用该类可以实现普遍意义上的多数据源管理功能.  1.扩 ...
  • 让云触手可及,微软云计算实践指南>,这三天我把这本书看了一遍,特写下一些读书笔记与想了解云.想了解微软云的你分享一下.互联网大转换的制高点——云计算,那本书上篇以电力的普及的过程来比喻信息技术的发展,本书同样引 ...
  • XenApp6.0部署之四配置LicenseServer
     在这一篇博文里面我要介绍一下如何安装配置License Server,license S ...