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 /ways_express_int_sum_pow.py | |
parent | 20f07f1feae9cf99ff005d379919fd9bad012f82 (diff) | |
download | leetcode-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.py | 37 |
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)) |