aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-13 09:58:49 +0200
committerJack Sangdahl <[email protected]>2025-08-13 09:58:49 +0200
commit129bb98a6f92b0e527d336cc8760efaaef6487d9 (patch)
treec490ce05498991f84dfe37e775f387d2f0fd23c8
parent07680f2c668dbc7c14b36badd9dcfe59a967c78e (diff)
downloadleetcode-129bb98a6f92b0e527d336cc8760efaaef6487d9.tar.gz
leetcode-129bb98a6f92b0e527d336cc8760efaaef6487d9.zip
326. power of three
-rw-r--r--power_of_three.c32
-rw-r--r--power_of_three.py7
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))