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