From 129bb98a6f92b0e527d336cc8760efaaef6487d9 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Wed, 13 Aug 2025 09:58:49 +0200 Subject: 326. power of three --- power_of_three.c | 32 +++++++------------------------- 1 file changed, 7 insertions(+), 25 deletions(-) (limited to 'power_of_three.c') 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 } -- cgit v1.2.3