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

|

350 Discussions

|

  • jmcparland
     + 0 comments

    Haskell

    Function wwo -- "with or without"

    module Main where

vals :: Int -> Int -> [Int]
vals n k = reverse $ takeWhile (<= n) [x ^ k | x <- [1 ..]]

wwo :: Int -> [Int] -> Int
wwo n xs
  | n == 0 = 1
  | n < 0 = 0
  | null xs = 0
  | otherwise = wwo n (tail xs) + wwo (n - head xs) (tail xs)

main :: IO ()
main = do
  n <- readLn :: IO Int
  k <- readLn :: IO Int
  print $ wwo n (vals n k)

  • 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;
}