aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-08-12 10:49:11 +0200
committerJack Sangdahl <[email protected]>2025-08-12 10:49:11 +0200
commit22ba93aab326c45f744503778d592c0623a058d5 (patch)
tree8995d7607b52e43c1bb65579fd4690db7ba7b2eb
parent20f07f1feae9cf99ff005d379919fd9bad012f82 (diff)
downloadleetcode-22ba93aab326c45f744503778d592c0623a058d5.tar.gz
leetcode-22ba93aab326c45f744503778d592c0623a058d5.zip
2787. ways to express an integers as sum of powers
-rw-r--r--ways_express_int_sum_pow.c43
-rw-r--r--ways_express_int_sum_pow.py37
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))