Not able to solve the power sum for all cases using recursion

user_17219787 0
Viewed 187

I have written the code of this problem but it works for only 70% of the test cases. I can't figure out what is wrong with it. Please help.

Problem:- Find the number of ways that a given integer, X, can be expressed as the sum of the Nth powers of unique, natural numbers in the range of [1,25] both inclusive.

Hint:-

The answer will be (1^2 + 3^2).

My code is not working for x = 100 and n = 2. The output should be 3 but it returns 33.

let x = 100;
let n = 2;
let num = 0;
let index = 1;

function power(x, n, num, index, ways = 0) {
  if (x === num) {
    return 1;
  }
  if (x < num) {
    return 0;
  }
  for (let i = index; i <= 25; i++) {
    ways += power(x, n, (num + ((i) ** n)), index + 1);
  }
  return ways;
}
console.log(power(x, n, num, index));

recursion javascript
1 Answers

Your logic is almost right. But you're not properly removing duplicate values and ending up including things like 9^2 + 3^2 + 3^2 + 1^2 or 5^2 + 5^2 + 5^2 + 4^2 + 3^2.

You need to change the recursive index you pass. You shouldn't use your index parameter but your loop iterator, i:

let x = 100;
let n = 2;
let num = 0;
let index = 1;

function power(x, n, num, index, ways = 0) {
  if (x === num) {
    return 1;
  }
  if (x < num) {
    return 0;
  }
  for (let i = index; i <= 25; i++) {
 // ways += power(x, n, (num + ((i) ** n)), index + 1);
 //                                         v-^
    ways += power(x, n, (num + ((i) ** n)), i + 1);
  }
  return ways;
}
console.log(power(x, n, num, index));

I figured this out fairly quickly by writing my own version of the function from scratch, and getting the exact same wrong result. I added some logging and realized the problem and was able to spot it quickly. This translated easily to your code.

But I think my function is cleaner, so I'm including it here. It does much the same logic, but in a cleaner functional manner:

const range = (lo, hi) => 
  Array .from ({length: hi - lo + 1}, (_, i) => i + lo)

const sum = (ns) =>
  ns .reduce ((a, b) => a + b, 0)

const countPowerSums = (n, p, i = 1) =>
  n < 0
    ? 0
  : n == 0
    ? 1
  : sum (range (i, 25) .map (b => countPowerSums (n - b ** p, p, b + 1)))

console .log (countPowerSums (100, 2))

user_12436410
Related