We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Recursion
  4. The Power Sum
  5. Discussions

The Power Sum

Sort by

recency

|

349 Discussions

|

  • SI006677Abhishek
     + 0 comments

    int findPows(int X, int num, int N) {

    int val = X - pow(num, N);
if (val < 0) {
    return 0;  
}
if (val == 0) {
    return 1;  
}

return findPows(val, num + 1, N) + findPows(X, num + 1, N);

    }

    int powerSum(int X, int N) { return findPows(X, 1, N); }

  • dehaka
     + 0 comments

    knapsack, O(X * X^(1/N))

    int powerSum(int X, int N) {
    int L = pow(X, 1.0/N);
    vector<vector<int>> cache(X+1, vector<int>(L+1));
    for (int j=0; j <= L; j++) cache[0][j] = 1;
    for (int i=1; i <= X; i++) {
        for (int j=1; j <= L; j++) {
            if (i < pow(j, N)) cache[i][j] = cache[i][j-1];
            else cache[i][j] = cache[i][j-1] + cache[i - pow(j, N)][j-1];
        }
    }
    return cache[X][L];
}

  • mrugiero
     + 0 comments

    I noticed X was capped to 1000 and I'd never need to try any number >sqrt(1000), which happens to be just under 32. So, what I did was precompute the Nth powers for [1..32], store my current set as a bitmap in a u32. and then add when the bit was on. I just iterated until the first power of 2 (which means it's a single element set) for which the sum (the actual Nth power, in this case) was > X, since that means it's the Nth root of X and thus no point trying anything else. I'm somewhat proud of how dumb my solution was. No recursion, no algorithms concepts (although that's what I'm here to train :'( ).

    fn powers(N: i32) -> [i32; 32] {
    let mut P = [0i32; 32];
    P[0] = 1;

    for (i, j) in (1..32usize).zip(2..33i32) {
        P[i] = j.pow(N as u32);
    }

    P
}
 
fn powerSumS(S: u32, P: &[i32]) -> i32 {
    let mut acc = 0;
    for bit in 0..32 {
        acc += P[bit] * (S & (1 << bit) != 0) as i32;
    }
    acc
}

fn powerSum(X: i32, N: i32) -> i32 {
    let mut current_set = 2u32;
    let mut count = 0;
    let P = powers(N);
    loop {
        let sum = powerSumS(current_set, &P);
        count += (sum == X) as i32;
        // We never need to explore further from sqrt(X)
        if current_set.is_power_of_two() && sum > X {
            break;
        }
        current_set += 1;
    }
    count
}

  • tj900model
     + 0 comments

    Simple C++ solution using Back Tracking:

    int findPows(int X, int num, int N) {
    int count=0;
    int val = X-pow(num,N);
    if (val>0) {
        num+=1;
    }
    else {
        if (val==0) {
            count+=1;
        }
        return count;
    }
    return findPows(val,num,N)+findPows(X,num,N);
}
int powerSum(int X, int N) {
    
    int count = 0;
    count = findPows(X, 1, N);
    
    return count;
}

  • khuatducminh_t67
     + 0 comments

    I coded in Java, using backtracking as the core algorithm in the solution. This can be improved. I recommend this problem for anyone who just learn backtracking.

    public static int powerSum(int X, int N) {
    // Write your code here
        return powerSum(X, N, 0);
    }
    
    static int powerSum(int X, int N, int min){
       /*
            My solution: try, check and try again (backtracking)
            Base cases: 
                X < 0 -> try but fail (+0) -> try again
                X == 0 -> try and find (+1) -> continues try
            ** Numbers tried must be increment, starting at least with 1. 
            -> Reduces duplicate cases.
            Induction steps:
                Find satisfied numbers, try one of them (k)
                Minus X to k^N(1 case - 1 subproblem)
            Time complex: O((floor(log_N(X)))!)
        */
        
        if(X < 0){
            return 0; 
        } 
        if(X == 0){
            return 1; //true because of (X >= 1) condition
        } 
    
        int count = 0;
        int i = min + 1;
        while(exp(i,N) <= X){ //O(log_N(X))
            count += powerSum(X - exp(i,N), N, i);
            i++;
        }
        
        return count;
    }
    
    private static int exp(int n, int N){
        int ex = n;
        for(int i = 1; i < N; i++){
            n *= ex;
        }
        return n;
    }