diff options
author | Jack Sangdahl <[email protected]> | 2025-08-13 09:58:49 +0200 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-13 09:58:49 +0200 |
commit | 129bb98a6f92b0e527d336cc8760efaaef6487d9 (patch) | |
tree | c490ce05498991f84dfe37e775f387d2f0fd23c8 | |
parent | 07680f2c668dbc7c14b36badd9dcfe59a967c78e (diff) | |
download | leetcode-129bb98a6f92b0e527d336cc8760efaaef6487d9.tar.gz leetcode-129bb98a6f92b0e527d336cc8760efaaef6487d9.zip |
326. power of three
-rw-r--r-- | power_of_three.c | 32 | ||||
-rw-r--r-- | power_of_three.py | 7 |
2 files changed, 13 insertions, 26 deletions
diff --git a/power_of_three.c b/power_of_three.c index d76dc75..dd1465f 100644 --- a/power_of_three.c +++ b/power_of_three.c @@ -2,33 +2,15 @@ #include "leetcode.h" /* - * power of 3 | decimal | bit - * -----------|---------|------ - * 3^0 | 1 | 00001 - * 3^1 | 3 | 00011 - * 3^2 | 9 | 01001 - * 3^3 | 27 | 11011 - * - * notice pattern in above bits: - * 3^1: 0b0001 + 0b0010 = 0b0011 (3) - * 3^2: 0b0011 + 0b0110 = 0b1001 (9) - * 3^3: 0b1001 + 0b10010 = 0b11011 (27) - * - * we can keep shifting 'tmp' left by 1 until 'n' is reached. initialise 'tmp' - * to 1 because the least power of 3 can be 0. if 'tmp' is exactly 'n', it is - * divisible by 3. returns false automatically when 'n' is negative + * given an integer 'n', return true if it is a power of three. otherwise, + * return false. an integer 'n' is a power of three, if there exists an integer + * 'x' such that 'n == 3^x' */ -bool isPowerOfThree(int n) { - long tmp = 1; - while (tmp < n) - tmp += tmp << 1; - return tmp == n; -} +bool isPowerOfThree(int n) { return n > 0 && !(1162261467 % n); } int main() { - printf("%d\n", isPowerOfThree(27)); // expect: 1 - printf("%d\n", isPowerOfThree(0)); // expect: 0 - printf("%d\n", isPowerOfThree(-1)); // expect: 0 - printf("%d\n", isPowerOfThree(6561)); // expect: 1 + printf("%d\n", isPowerOfThree(27)); // expect: 1 + printf("%d\n", isPowerOfThree(0)); // expect: 0 + printf("%d\n", isPowerOfThree(-1)); // expect: 0 } diff --git a/power_of_three.py b/power_of_three.py index 7349ee4..946b7fd 100644 --- a/power_of_three.py +++ b/power_of_three.py @@ -1,5 +1,11 @@ # 326. Power of Three +""" +given an integer 'n', return true if it is a power of three. otherwise, +return false. an integer 'n' is a power of three, if there exists an integer +'x' such that 'n == 3^x' +""" + class Solution(object): def isPowerOfThree(self, n): @@ -17,4 +23,3 @@ if __name__ == "__main__": print(obj.isPowerOfThree(27)) print(obj.isPowerOfThree(0)) print(obj.isPowerOfThree(-1)) - print(obj.isPowerOfThree(6561)) |