Leetcode # 6922. Ways to Express an Integer as Sum of Powers

https://leetcode.com/contest/biweekly-contest-109/problems/ways-to-express-an-integer-as-sum-of-powers/

Solution

當你需要的是出現的次數而無關順序時
⇒ 使用 list Counter

Time Complexity: O()
Space Complexity: O()
(The input and output generally do not count towards the space complexity.)

class Solution:
  def numberOfWays(self, n: int, x: int) -> int:
    limit_n = n ** (1/x)
    posible_sets = collections.Counter()
    posible_sets[0] = 1
    for i in range(1, int(limit_n + 1.1)): # 0.1 for Floating-point Error
      new_posible_sets = collections.Counter()
      for key in posible_sets:
        new_result = key + i ** x
        if new_result <= n:
          new_posible_sets[new_result] += posible_sets[key]
      for key in new_posible_sets:
        posible_sets[key] += new_posible_sets[key]
    return posible_sets[n] % (10 ** 9 + 7)

#FloatingPointError

Last Updated on 2023/08/16 by A1go