[Hacker Rank] The Power Sum

The Power Sum

  • Time : O(xn)
  • Space : O(xn)
1
2
3
4
5
6
7
8
9
10
11
int dp[1000][1000];
int helper(int X, int p, int now) {
if(dp[X][now] != -1) return dp[X][now];
if(pow(now, p) > X) return 0;
if(pow(now, p) == X) return 1;
int& res = dp[X][now] = helper(X - pow(now, p), p, now + 1) + helper(X, p, now + 1);
return res;
}
int powerSum(int X, int N) {
return helper(X, N, 1);
}
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/06/16/PS/HackerRank/the-power-sum/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.