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 ...
一周排行
  • 观察者模式定义了一种一对多的依赖关系,让多个观察者对象同时监听某一个主题对象.这个主题对象在状态上发生变化时,会通知所有观察者对象,让他们能够自动更新自己.今天我们通过模拟按钮的处理事件来深入Java观察者模式的学习 ...
  • 西城110/linux高级作业12.26
    Insert into niu values (1, ‘lilei’, ‘F’, ‘1’, ...
  • 第三章、文件权限
      文中有借鉴鸟哥的部分内容,然后加上了自己的一些理解.一.文件权限的基本认识[root@ ...
  • XP系统,无法创建新的网络连接
    系统是XP,网络连接文件夹始终是空的.而且不能创建.所以系统托盘里的连接图标也没有,新建的 ...
  • Linux学习笔记——进程查看及管理
    Linux进程查看和管理工具有很多pstree命令:以树形方式显示进程    ps [OP ...
  • 在Oracle10g下,GATHER_STATS_JOB作业默认会定时自动运行,来收集数据库对象的统计信息,这些统计信息收集后,会做为Oracle CBO优化器模式的一个重要判断依据.同时,当对象的行数被修改超过10 ...
  •   关于目录或文件的ACL设定  1.首先确定文件系统是否开启了ACL功能使用mount命令查看,如果存在/dev/hda1 on / type ext3 (rw,acl说明已经开启)如果没有开启的话重新挂载开启ac ...
  • 一.配置ARP Inspection-添加静态arp条目hostname(config)# arp outside 10.1.1.1 0009.7cbe.2100-打开ARP Inspectionhostname(c ...
  • hostname ciscoasa          #配置主机名domain-name default.domain.invalid enable password oRmx3R1CItyN8X6z encrypt ...
  • 我的环境是Windows 2003的活动目录单域多站点架构,我所在的站点有一台域控制器和多台成员服务器:现在的情况是我的成员服务器上,如果我修改了时间,再通过命令行执行w32tm /resync时可以自动跟域控制器同 ...