Ways to Express an Integer as Sum of Powers

Ways to Express an Integer as Sum of Powers - Problem

Dynamic Programming Medium

Given two positive integers n and x.

Return the number of ways n can be expressed as the sum of the xth power of unique positive integers, in other words, the number of sets of unique integers [n1, n2, ..., nk] where n = n1^x + n2^x + ... + nk^x.

Since the result can be very large, return it modulo 10^9 + 7.

Example: If n = 160 and x = 3, one way to express n is n = 2^3 + 3^3 + 5^3.

Input & Output

Example 1 — Basic Case

$ Input: n = 10, x = 2

› Output: 1

💡 Note: Only one way: 10 = 1² + 3² = 1 + 9. We use unique positive integers 1 and 3.

Example 2 — Multiple Ways

$ Input: n = 4, x = 1

› Output: 5

💡 Note: Five ways to express 4 as sum of unique positive integers: {4}, {1,3}, {1,2,1} is invalid (1 repeated), so we have {4}, {1,3} only. Wait, let me recalculate: {4}, {1,3} are the only valid ways using unique integers. Actually: 4¹=4, or 1¹+3¹=4. So 2 ways.

Example 3 — Larger Input

$ Input: n = 160, x = 3

› Output: 5

💡 Note: Multiple ways to express 160 as sum of unique cubes. One example: 2³ + 3³ + 5³ = 8 + 27 + 125 = 160.

Constraints

1 ≤ n ≤ 300
1 ≤ x ≤ 5

Visualization

Tap to expand

Understanding the Visualization

Input

n=10, x=2 (find ways to express 10 as sum of unique squares)

Consider Powers

Available: 1²=1, 2²=4, 3²=9, 4²=16, ...

Find Combinations

Only valid: 1² + 3² = 1 + 9 = 10

Key Takeaway

🎯 Key Insight: This is a subset sum problem with power constraints - use DP to systematically count valid unique combinations

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to recognize this as a variant of the subset sum problem where we can choose unique positive integers whose x-th powers sum to n. The optimal approach uses dynamic programming to count combinations systematically. Time: O(n×√n), Space: O(n×√n).

Common Approaches

Approach	Time	Space	Notes
✓ 2D Dynamic Programming	O(n × √n)	O(n × √n)	Bottom-up DP table where dp[i][sum] represents ways using first i powers to make sum
Memoized Recursion	O(n × √n)	O(n × √n)	Add memoization to recursive approach to avoid recomputing same subproblems
Recursive Backtracking	O(2ⁿ)	O(n)	Try all possible combinations of power values using recursion

2D Dynamic Programming — Algorithm Steps

Create dp[maxNum][n+1] table
Initialize base cases: dp[i][0] = 1
For each number and sum, decide include/exclude
Return dp[maxNum][n]

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[i][0] = 1 for all i (one way to make sum 0)

Fill Table

For each number and sum, decide include/exclude

Result

dp[maxNum][n] contains final answer

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MOD 1000000007

int solution(int n, int x) {
    // Find maximum number whose power is <= n
    int maxNum = 1;
    while (pow(maxNum + 1, x) <= n) {
        maxNum++;
    }
    
    // Allocate dp table
    long long** dp = (long long**)malloc((maxNum + 1) * sizeof(long long*));
    for (int i = 0; i <= maxNum; i++) {
        dp[i] = (long long*)calloc(n + 1, sizeof(long long));
    }
    
    // Base case: 1 way to make sum 0
    for (int i = 0; i <= maxNum; i++) {
        dp[i][0] = 1;
    }
    
    for (int i = 1; i <= maxNum; i++) {
        long long powerVal = (long long)pow(i, x);
        for (int j = 0; j <= n; j++) {
            // Don't include number i
            dp[i][j] = dp[i-1][j];
            
            // Include number i if possible
            if (j >= powerVal) {
                dp[i][j] = (dp[i][j] + dp[i-1][j - powerVal]) % MOD;
            }
        }
    }
    
    int result = dp[maxNum][n];
    
    // Free memory
    for (int i = 0; i <= maxNum; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return result;
}

int main() {
    int n, x;
    scanf("%d", &n);
    scanf("%d", &x);
    printf("%d\n", solution(n, x));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × √n)

Nested loops: outer loop runs √n times (max numbers), inner loop runs n times

✓ Linear Growth

Space Complexity

O(n × √n)

2D DP table stores √n × n values

⚡ Linearithmic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler