Ways to Express an Integer as Sum of Powers | Leetcode 2787

//C++: Tabulation 1D
class Solution {
    #define MOD 1000000007

    int binaryExponentiation(int a,int b){
        int res = 1;
        while(b){
            if(b&1)
                res *= a;
            a *= a;
            b /= 2;
        }
        return res;
    }
public:
    int numberOfWays(int n, int x) {
        // Step-1: Calculate powers array
        vector<int> powers;
        for(int i=1;i<=n;++i){
            int power = binaryExponentiation(i,x);
            if(power>n)//Can't include any more powers
                break;
            
            powers.push_back(power);
        }
        // Step-2: Apply Tabulation
        vector<int> dp(n+1);
        dp[0] = 1;
        int p = powers.size();
        for(int pos=1;pos<=p;++pos){
            for(int target=n;target>=powers[pos-1];--target){
                dp[target] = (dp[target] + dp[target-powers[pos-1]]) % MOD;
            }
        }
        return dp[n];
    }
};

//C++: Tabulation: 2D
class Solution {
    #define MOD 1000000007

    int binaryExponentiation(int a,int b){
        int res = 1;
        while(b){
            if(b&1)
                res *= a;
            a *= a;
            b /= 2;
        }
        return res;
    }
public:
    int numberOfWays(int n, int x) {
        // Step-1: Calculate powers array
        vector<int> powers;
        for(int i=1;i<=n;++i){
            int power = binaryExponentiation(i,x);
            if(power>n)//Can't include any more powers
                break;
            
            powers.push_back(power);
        }
        // Step-2: Apply Tabulation
        int p = powers.size();
        vector<vector<int>> dp(p+1,vector<int>(n+1,0));
        
        for(int pos=1;pos<=p;++pos){
            dp[pos-1][0] = 1;
            for(int target=1;target<=n;++target){
                if(powers[pos-1]>target)
                    dp[pos][target] = dp[pos-1][target];
                else
                    dp[pos][target] = (dp[pos-1][target] + dp[pos-1][target-powers[pos-1]]) % MOD;
            }
        }
        return dp[p][n];
    }
};

//C++: Recursion + Memoization
class Solution {
    #define MOD 1000000007
    vector<int> value;
    int mem[300+2][300+2];

    int binaryExponentiation(int a,int b){
        int res = 1;
        while(b){
            if(b&1)
                res *= a;
            a *= a;
            b /= 2;
        }
        return res;
    }
    int findWays(int pos,int target){
        if(target==0)                           return 1;//Valid combination
        if(pos==value.size() or target<0)       return 0;//Invalid
        if(mem[pos][target]!=-1)                return mem[pos][target];

        int exclude = findWays(pos+1,target);
        int include = findWays(pos+1,target-value[pos]);
        return mem[pos][target] = (exclude + include) % MOD;
    }
public:
    int numberOfWays(int n, int x) {
        for(int i=1;i<=n;++i){
            int power = binaryExponentiation(i,x);
            if(power>n)//Can't include any more powers
                break;
            
            value.push_back(power);
        }
        memset(mem,-1,sizeof(mem));
        return findWays(0,n);
    }
};

/*
import java.util.*;

public class Solution {
    private static final int MOD = 1_000_000_007;

    // Compute a^b but stop and return limit+1 if it exceeds limit
    private long powWithLimit(int a, int b, int limit) {
        long res = 1;
        for (int i = 0; i < b; ++i) {
            res *= a;
            if (res > limit) return (long)limit + 1;
        }
        return res;
    }

    // Tabulation 1D (space optimized)
    public int numberOfWays1D(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int val : powers) {
            for (int t = n; t >= val; --t) {
                dp[t] = (int)((dp[t] + dp[t - val]) % MOD);
            }
        }
        return dp[n];
    }

    // Tabulation 2D
    public int numberOfWays2D(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }
        int pcount = powers.size();
        int[][] dp = new int[pcount + 1][n + 1];

        for (int i = 0; i <= pcount; ++i) dp[i][0] = 1;

        for (int i = 1; i <= pcount; ++i) {
            int val = powers.get(i - 1);
            for (int t = 1; t <= n; ++t) {
                if (val > t) dp[i][t] = dp[i - 1][t];
                else dp[i][t] = (int)((dp[i - 1][t] + dp[i - 1][t - val]) % MOD);
            }
        }
        return dp[pcount][n];
    }

    // Recursion + Memoization
    public int numberOfWaysRec(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }
        int pcount = powers.size();
        int[][] mem = new int[pcount][n + 1];
        for (int i = 0; i < pcount; ++i) Arrays.fill(mem[i], -1);

        return findWays(0, n, powers, mem);
    }

    private int findWays(int pos, int target, List<Integer> powers, int[][] mem) {
        if (target == 0) return 1;
        if (pos == powers.size() || target < 0) return 0;
        if (mem[pos][target] != -1) return mem[pos][target];

        int exclude = findWays(pos + 1, target, powers, mem);
        int include = 0;
        int val = powers.get(pos);
        if (target - val >= 0) include = findWays(pos + 1, target - val, powers, mem);

        mem[pos][target] = (int)((exclude + (long)include) % MOD);
        return mem[pos][target];
    }

    // Example runner
    public static void main(String[] args) {
        Solution s = new Solution();
        int n = 10, x = 2;
        System.out.println(s.numberOfWays1D(n, x));
        System.out.println(s.numberOfWays2D(n, x));
        System.out.println(s.numberOfWaysRec(n, x));
    }
}

import java.util.*;

public class Solution {
    private static final int MOD = 1_000_000_007;

    // Compute a^b but stop and return limit+1 if it exceeds limit
    private long powWithLimit(int a, int b, int limit) {
        long res = 1;
        for (int i = 0; i < b; ++i) {
            res *= a;
            if (res > limit) return (long)limit + 1;
        }
        return res;
    }

    // Tabulation 1D (space optimized)
    public int numberOfWays1D(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }

        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int val : powers) {
            for (int t = n; t >= val; --t) {
                dp[t] = (int)((dp[t] + dp[t - val]) % MOD);
            }
        }
        return dp[n];
    }

    // Tabulation 2D
    public int numberOfWays2D(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }
        int pcount = powers.size();
        int[][] dp = new int[pcount + 1][n + 1];

        for (int i = 0; i <= pcount; ++i) dp[i][0] = 1;

        for (int i = 1; i <= pcount; ++i) {
            int val = powers.get(i - 1);
            for (int t = 1; t <= n; ++t) {
                if (val > t) dp[i][t] = dp[i - 1][t];
                else dp[i][t] = (int)((dp[i - 1][t] + dp[i - 1][t - val]) % MOD);
            }
        }
        return dp[pcount][n];
    }

    // Recursion + Memoization
    public int numberOfWaysRec(int n, int x) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 1; i <= n; ++i) {
            long p = powWithLimit(i, x, n);
            if (p > n) break;
            powers.add((int)p);
        }
        int pcount = powers.size();
        int[][] mem = new int[pcount][n + 1];
        for (int i = 0; i < pcount; ++i) Arrays.fill(mem[i], -1);

        return findWays(0, n, powers, mem);
    }

    private int findWays(int pos, int target, List<Integer> powers, int[][] mem) {
        if (target == 0) return 1;
        if (pos == powers.size() || target < 0) return 0;
        if (mem[pos][target] != -1) return mem[pos][target];

        int exclude = findWays(pos + 1, target, powers, mem);
        int include = 0;
        int val = powers.get(pos);
        if (target - val >= 0) include = findWays(pos + 1, target - val, powers, mem);

        mem[pos][target] = (int)((exclude + (long)include) % MOD);
        return mem[pos][target];
    }

    // Example runner
    public static void main(String[] args) {
        Solution s = new Solution();
        int n = 10, x = 2;
        System.out.println(s.numberOfWays1D(n, x));
        System.out.println(s.numberOfWays2D(n, x));
        System.out.println(s.numberOfWaysRec(n, x));
    }
}
*/