【LeetCode】Power of Three問題解決レポート
1030 ワード
Power of Three
[LeetCode]
https://leetcode.com/problems/power-of-three/
Total Accepted: 38705 Total Submissions: 105634 Difficulty: Easy
Question
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?
Ways
第一感覚は簡単ですね.followupを見ると再帰とループを使わなくてもいいかどうか.それは数学の問題に違いない.
法則を探そうと思って、1つの法則だけを見つけて、9以上の3のべき乗の各位の和はすべて9で除けることができます......しかし例えば18、1+8も9で除けることができますが、3の倍数ではありません.
仕方がない,ほかの人がどう書いたか見てみよう.あまり賢くないようですね.
対数をとる.1つの数が3をベースにした対数が整数であるかどうかを見ます.まあ、頭がいいですね.
AC:20ms
もう1つの方法は,まず最大の3のべき乗のintを見つけて,nがこの数を除去できるかどうかを見ることである.効率はこれより高いはずで、試していません.以下を参照してください.
Date
2016/5/1 16:47:54
[LeetCode]
https://leetcode.com/problems/power-of-three/
Total Accepted: 38705 Total Submissions: 105634 Difficulty: Easy
Question
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?
Ways
第一感覚は簡単ですね.followupを見ると再帰とループを使わなくてもいいかどうか.それは数学の問題に違いない.
法則を探そうと思って、1つの法則だけを見つけて、9以上の3のべき乗の各位の和はすべて9で除けることができます......しかし例えば18、1+8も9で除けることができますが、3の倍数ではありません.
仕方がない,ほかの人がどう書いたか見てみよう.あまり賢くないようですね.
対数をとる.1つの数が3をベースにした対数が整数であるかどうかを見ます.まあ、頭がいいですね.
public class Solution {
public boolean isPowerOfThree(int n) {
return (Math.log10(n)/Math.log10(3)) % 1 == 0;
}
}
AC:20ms
もう1つの方法は,まず最大の3のべき乗のintを見つけて,nがこの数を除去できるかどうかを見ることである.効率はこれより高いはずで、試していません.以下を参照してください.
public boolean isPowerOfThree(int n) {
return n>0 && Math.pow(3, (int)(Math.log(0x7fffffff)/Math.log(3)))%n==0;
}
Date
2016/5/1 16:47:54