aboutsummaryrefslogtreecommitdiff
path: root/ways_express_int_sum_pow.py
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 /ways_express_int_sum_pow.py
parent20f07f1feae9cf99ff005d379919fd9bad012f82 (diff)
downloadleetcode-22ba93aab326c45f744503778d592c0623a058d5.tar.gz
leetcode-22ba93aab326c45f744503778d592c0623a058d5.zip
2787. ways to express an integers as sum of powers
Diffstat (limited to 'ways_express_int_sum_pow.py')
-rw-r--r--ways_express_int_sum_pow.py37
1 files changed, 37 insertions, 0 deletions
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))