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
}
|