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 ...
一周排行
  • 内容简介1.第二部分第六课:Nano,初学者的文本编辑器2.第二部分第七课预告:软件安装,如虎添翼Nano,初学者的文本编辑器这一课比较简单,没有什么太难的概念.不过这一课会讲如何配置终端噢.大家可以泡个泡面,烤只烤 ...
  • CCNA视频:EIGRP专题实验3:EIGRP多AS号问题研究
    1:配置地址(略),并配置EIGRP多个ASR1(config)#routereigrp ...
  •  mysql安装:    1> 解压 .zip文件    2> 编辑系统环境变量Path ,  添加 ;E:\Program Files\mysql56\bin    3> 复制my-default ...
  • 昨天体验了一下微软新出炉的"Windows Server 2008 RC1 Enterprise测试版":代号"Viridian" 的Hyper-V的企业版.在其主打的虚拟化技 ...
  • 折腾了好久,终于在Github上搭建了自己的博客.这里面总结一下过程希望对大家能有所帮助. Github建博优缺点 和 csdn,新浪,网易相比,在Github上可以自己实现功能 和阿里云,VPS相比,github托 ...
  •  在计算机科学中,bit是表示信息的最小单位,叫做二进制位:一般用0和1表示.Byte叫做字节,由8个位(8bit)组成一个字节(1Byte),用于表示计算机中的一个字符.bit(比特)与Byte(字节)之间可以进行 ...
  • iOS8.0后使用UIAlertController
    iOS 8的新特性之一就是让接口更有适应性.更灵活,因此许多视图控制器的实现方式发生了巨大 ...
  • ffmpeg转码问题一:反交错
    http://www.front2end.cn/Post/Detail/40ffmpeg ...
  • s = random = N= Point p = Iterator<Point> it = Point temp = foodX = Math.abs(random.nextInt()) % foodY ...
  •  MySQL数据库支持数据库的主从复制功能,因此在集群方面具有其独特的优势,国内外大型网站架构体系中,均采用了MySQL的主从数据库配置来实现查询负载.数据库热备等功能.本人在此将如何配置实现做了个简单小结. 服务器 ...