aboutsummaryrefslogtreecommitdiff
path: root/power_of_three.c
blob: d76dc752592f753c0b293eb0647db351ac24baeb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 326. Power of Three
#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
 */

bool isPowerOfThree(int n) {
  long tmp = 1;
  while (tmp < n)
    tmp += tmp << 1;
  return tmp == 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
}