aboutsummaryrefslogtreecommitdiff
path: root/check_num_sum_pow3.c
blob: 67fe29986e5627293f7ab3db223748a88d503ed0 (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
// 1780. Check if Number is a Sum of Powers of Three
#include "leetcode.h"

/*
 * given an integer 'n', return true if it is possible to represent 'n' as the
 * sum of distinct powers of three. otherwise, return false. an integer 'y' is a
 * power of three if there exists an integer 'x' such that 'y == 3^x'
 */

bool checkPowersOfThree(int n) {
  static int pow3[] = {4782969, 1594323, 531441, 177147, 59049,
                       19683,   6561,    2187,   729,    243,
                       81,      27,      9,      3,      1};
  for (int i = 0; i < 15; i++)
    if (n >= 2 * pow3[i])
      return false;
    else if (n >= pow3[i])
      n -= pow3[i];
  return true;
}

int main() {
  printf("%d\n", checkPowersOfThree(12)); // expect: 1
  printf("%d\n", checkPowersOfThree(91)); // expect: 1
  printf("%d\n", checkPowersOfThree(21)); // expect: 0
}