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
     + 1 comment

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

    • mihrandovlatyan
       + 1 comment

      I think this is the best solution.

      • jufena84
         + 0 comments

        i don't really know, for example, we have 800, the square root is 28.3, we can take int 28, it means each number square higher than 28 results higher than 800, so, we can only take numbers <28, i don't think that we can find 561 combinations of unique square numbers between 1 and 28.

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

Join us

Create a HackerRank account

Be part of a 26 million-strong community of developers

Already have an account?Log in