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

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