LeetCode 326 - Power of Three


http://www.hrwhisper.me/leetcode-power-of-three/
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?
    bool isPowerOfThree(int n) {
        if(n <= 0) return false;
        while(n > 1){
            if(n %3 != 0) return false;
             n/=3;
        }
        return true;
    }
bool isPowerOfThree(int n) {
if (n <= 0) return false;
if (n == 1) return true;
return n % 3 == 0 && isPowerOfThree(n / 3);
}

bool isPowerOfThree(int n) {
return n <= 0 ? false : n == pow(3, round(log(n) / log(3)));
}
http://algobox.org/power-of-three/
A trivial loop / recursion solution is to divide the number by 3 and look at the remainder again and again.
Another idea is based on logarithm rules and float numbers which i don’t like very much. After all the log function it self may actually implemented using loop / recursion.
Since the 32 bit signed integer has at most 20 numbers, here is a list.
If we put them in a hash set beforehand, then we can query is power of three in O(1) time. I have seen people write in python like this
Python
Although it seems not using any loop, the in operation for list in python takes linear time, which indicating a loop underneath. We can use a set instead and put it into a class variable so we can share between calls.
Cheating Method
This is not really a good idea in general. But for such kind of power questions, if we need to check many times, it might be a good idea to store the desired powers into an array first
public boolean isPowerOfThree(int n) {
    HashSet<Integer> set = new HashSet<>(Arrays.asList(1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 1162261467));
    return set.contains(n);
}
Python
However, the fastest solution is this
Java
This works because 3 is a prime number. A 32 bit positive integer is a power of 3 is equivalent to it is a factor of 3^19 = 1162261467.
This doesn’t work for composite number like 4 or 6.

X.
Radix-3 original post
The idea is to convert the original number into radix-3 format and check if it is of format 10* where 0* means k zeros with k>=0.
public boolean isPowerOfThree(int n) {
    return Integer.toString(n, 3).matches("10*");
}
http://www.cnblogs.com/grandyang/p/5138212.html
题目中的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);
    }
};
http://fujiaozhu.me/?p=799
    bool isPowerOfThree(int n) {
        if(n == 0) return false;
        else return log10(n)/log10(3) - (int)(log10(n)/log10(3)) < 1e-15;
    }

https://discuss.leetcode.com/topic/36150/1-line-java-solution-without-loop-recursion
public boolean isPowerOfThree(int n) {
    // 1162261467 is 3^19,  3^20 is bigger than int  
    return ( n>0 &&  1162261467%n==0);
}
https://discuss.leetcode.com/topic/33536/a-summary-of-all-solutions-new-method-included-at-15-30pm-jan-8th
Two trivial solutions first:
#Recursive Solution#
public boolean isPowerOfThree(int n) {
    return n>0 && (n==1 || (n%3==0 && isPowerOfThree(n/3)));
}
#Iterative Solution#
update following Stefan's answer below:
public boolean isPowerOfThree(int n) {
    if(n>1)
        while(n%3==0) n /= 3;
    return n==1;
}

http://blog.csdn.net/u014688145/article/details/53417543
public boolean isPowerOfK(int n,int k) { if (n < 1) { return false; } while (n % k == 0) { n /= k; } return n == 1; }
其中231.Power of Three可以利用二进制进行求解。在对问题没有思路的时候,我们可以heuristic,很自然的想法我们把十进制的数表示成二进制,例如:
1 -> 0001 
2 -> 0010 
4 -> 0100 
8 -> 1000
由此,我们可以简单猜测它power of two,就是在二进制中,出现其中1位是1的情况,其他均为0。有了这猜测,我们只需要从数学上论证它是正确的即可,这里就不再论证了,答案显而易见。
public boolean isPowerOfTwo(int n){ int count =0; while (n >0){ count += (n&(0x01)); n >>=1; } return count ==1; }
那么对于236题,同样适用嘛?吼吼,咱们继续heuristic下,例如
1 -> 0001 
3 -> 0011 
9 -> 1001 
27 -> 11011
这规律不太对啊,嗯,在二进制中你着实找不到关于power of Three的一般规律。由此,上述这算法并非是通用的。那应该怎么办呢?power of Two和power of Three真的没有一点联系嘛?
我们换个维度考虑问题,所给的数都是十进制的数,而算法2.是把十进制的数映射到了二进制上,因为我们求的是power of Two,那么我们就必须映射到二进制上去嘛?为什么我们会自然而然的把十进制映射到二进制上去,至少我在得知这种解法时,脑中出现的第一反应是计算机是天然的用二进制来表达任何东西的。然而思维的局限性由此产生,想着同样的power of Three就一定要映射到二进制去解决嘛?由此,我得出两个结论:
  • 问题的本质或者说算法的求解不应该局限于计算机固有的属性,它是游离于计算机体系之外的,只是我们在实际编写代码时,需要考虑计算机体系知识而已。
  • 分析问题一定要抓住关键点,power of Two只是一般模式中的一个特例而已,如果单纯的为这个特例设计算法,那么每当遇到新的问题时,往往苦恼不堪,因为并没有抽象出通解。
回到上述问题,原本并非想着要写出power of Two 十进制到二进制的映射关系,但为了分析问题本质,也必须写一下
考虑power of Ten.你会发现,这个问题很容易解,因为在1,10,100,1000,…..,你只需要统计1出现的个数为1,且其它位都属于0即可。power of Two,我们是把数映射到了二进制表示法,同样地有: 
i=0len(s)1s[i]2i

由此power of Three,我们就能想着是否只需要把十进制的power of Three映射到三进制上去即可,然后在三进制的表示域中找出它的规律,并求解答案: 

i=0len(s)1s[i]3i

得到:
1 -> 000_001 
3 -> 000_010 
9 -> 000_100 
27 -> 001_000
public boolean isPowerOfThree(int n) { return Integer.toString(n, 3).matches("^10*$"); }
主要内容结束了,作为程序员,本着精益求精的精神,把leetCode中介绍的其他算法补充完整。
数学方法:n=3i 
i=log3(n)=logb(n)logb(3)
public boolean isPowerOfThree(int n) { return (Math.log10(n) / Math.log10(3)) % 1 == 0; }
判断i是否为整数即可。这是最直接了当的解法,俗称最终解,计算机一步得到结果。
但这是有问题的,因为在log10(n)/log10(3)中,计算机求得的实际解可能为5.0000001 or 4.9999999,所以我们还是用误差来优化该算法吧。
return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;
  • 1
  • 1
至于leetCode官方提供的最后一种方法,暂时还未研究,等有时间再补充吧。

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts