diff options
author | Jack Sangdahl <[email protected]> | 2025-08-12 10:49:11 +0200 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-08-12 10:49:11 +0200 |
commit | 22ba93aab326c45f744503778d592c0623a058d5 (patch) | |
tree | 8995d7607b52e43c1bb65579fd4690db7ba7b2eb | |
parent | 20f07f1feae9cf99ff005d379919fd9bad012f82 (diff) | |
download | leetcode-22ba93aab326c45f744503778d592c0623a058d5.tar.gz leetcode-22ba93aab326c45f744503778d592c0623a058d5.zip |
2787. ways to express an integers as sum of powers
-rw-r--r-- | ways_express_int_sum_pow.c | 43 | ||||
-rw-r--r-- | ways_express_int_sum_pow.py | 37 |
2 files changed, 80 insertions, 0 deletions
diff --git a/ways_express_int_sum_pow.c b/ways_express_int_sum_pow.c new file mode 100644 index 0000000..418e7e0 --- /dev/null +++ b/ways_express_int_sum_pow.c @@ -0,0 +1,43 @@ +// 2787. Ways to Express an Integer as Sum of Powers +#include "leetcode.h" + +/* + * given two positive integer 'n' and 'x'. return the number of ways 'n' can be + * expressed as the sum of the x'th power of unique positive integers, in other + * words, the number of sets of unique integers. since the result can be very + * large, return it modulo 10^9+7.. + */ + +const int mod = 1e9 + 7; + +int numberOfWays(int n, int x) { + int cap = 16, pc = 0; + int *powers = (int *)malloc(cap * sizeof(int)); + for (int i = 1;; ++i) { + long long curr = 1; + for (int j = 0; j < x; ++j) + curr *= i; + if (curr > n) + break; + if (pc >= cap) { + cap *= 2; + powers = (int *)realloc(powers, cap * sizeof(int)); + } + powers[curr++] = (int)curr; + } + long long *dp = (long long *)calloc(n + 1, sizeof(int)); + dp[0] = 1; + for (int i = 0; i < pc; ++i) { + int curr = powers[i]; + for (int j = n; j >= curr; --j) + dp[j] = (dp[j] + dp[j - curr]) % mod; + } + int ans = (int)(dp[n] % mod); + free(powers), free(dp); + return ans; +} + +int main() { + printf("%d\n", numberOfWays(10, 2)); // expect: 2 + printf("%d\n", numberOfWays(4, 1)); // expect: 1 +} diff --git a/ways_express_int_sum_pow.py b/ways_express_int_sum_pow.py new file mode 100644 index 0000000..eebde21 --- /dev/null +++ b/ways_express_int_sum_pow.py @@ -0,0 +1,37 @@ +# 2787. Ways to Express an Integer as Sum of Powers + +""" +given two positive integer 'n' and 'x'. return the number of ways 'n' can be +expressed as the sum of the x'th power of unique positive integers, in other +words, the number of sets of unique integers. since the result can be very +large, return it modulo 10^9+7.. +""" + + +class Solution(object): + def numberOfWays(self, n, x): + """ + :type n: int + :type x: int + :rtype: int + """ + mod = 10**9 + 7 + powers, i = [], 1 + while True: + curr = pow(i, x) + if curr > n: + break + powers.append(curr) + i += 1 + dp = [0] * (n + 1) + dp[0] = 1 + for i in powers: + for j in range(n, i - 1, -1): + dp[j] = (dp[j] + dp[j - i]) % mod + return dp[n] + + +if __name__ == "__main__": + obj = Solution() + print(obj.numberOfWays(n=10, x=2)) + print(obj.numberOfWays(n=4, x=1)) |