Given an array of length n, consolidate the sum created by adding index pairs until there's only a single index.
EXAMPLES:
[1, 2, 3, 4, 5] => 48
Explanation:
- The next array would be [3, 5, 7, 9] because [1 2, 2 3, 3 4, 4 5]
- The next array would be [8, 12, 16] because [3 5, 5 7, 7 9]
- The next array would be [20, 28] because [8 12, 12 16]
- The final answer would be [48] because [20 28] and there are not enough operands to add
This is the solution I came up with but I feel like there's a simpler way to achieve the same solution. I'm trying to understand recursion but I need some explanation on why when we call our stacks, we do it from the (n - 1) or from the (n 1) to reach our base cases and how do we know which one to use? I don't understand why we're using those passing arguments when we are returning our helper function.
function reduceSum(input) {
function simplify(input, index) {
if (index === 1) {
return input[0];
}
if (index === 0) {
return 0;
}
for (let i = 0; i < input.length; i ) {
input[i] = input[i 1];
}
return simplify(input, index - 1);
}
return simplify(input, input.length);
}
console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)CodePudding user response：
I'm not sure the following is a genuinely simpler way to achieve the solution as it does basically the same thing (although it does not modify the original array), but perhaps there's something useful here:
function reduceSum(input) {
if(input.length <= 1)
return input[0] || 0;
return reduceSum(
input.reduce(
(acc, val, i, { [i 1]: next }) =>
typeof next !== 'undefined' ? [ ...acc, val next ] : acc,
[]
)
);
}
console.log(reduceSum([1, 2, 3, 4]) == 20)
console.log(reduceSum([5]) == 5)
console.log(reduceSum([]) == 0)
console.log(reduceSum([1, 3, 5]) == 12)
console.log(reduceSum([-5, 5]) == 0)
console.log(reduceSum([-5, 5, -5, 5]) == 0)
console.log(reduceSum([-5, 5, 5, -5]) == 20)The next variable is populated using object destructuring on the array argument passed to the reduce callback function. It will be undefined when the reduce method processes the last element of the array, this last element gets skipped; this means that each time we run reduceSum the array gets shorter by one element (as per your original).
CodePudding user response：
Each loop updates values in the array. And with each loop the index needs to be reduced, otherwise it will be infinite loop. Just add console.log("" input) right after the for loop and you'll see how input progresses with each call of simplify() function.
There are a few optimizations can be done to your code:
- you don't need
simplify()at all, simply check ifindexvariable isundefined:
function reduceSum(input, index) {
if (index === undefined)
index = input.length;
if (index === 1) {
return input[0];
}
if (index === 0) {
return 0;
}
for (let i = 0; i < input.length; i ) {
input[i] = input[i 1];
}
console.log("input: " input);
return reduceSum(input, index - 1);
}
console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)- You can also optimize a little by only looping through 0 to
index - 1instead of entire array:
function reduceSum(input, index) {
if (index === undefined)
index = input.length;
if (index === 1) {
return input[0];
}
if (index === 0) {
return 0;
}
for (let i = 0; i < index - 1; i ) {
input[i] = input[i 1];
}
console.log("input: " input);
return reduceSum(input, index - 1);
}
console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)- Further you can optimize the code by adding default value to the
indexvariable and moving conditions to the end the function, this way it won't need an extra call of the function to get final result:
function reduceSum(input, index = input.length - 1) {
for (let i = 0; i < index; i ) {
input[i] = input[i 1];
}
console.log("input: " input);
if (index > 1)
return reduceSum(input, --index);
//return final result or 0 if array is empty
return input[0] || 0;
}
console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)- Finally, you can get rid of
indexall together, by removing last item from theinputarray instead, this method is slower than the above though:
function reduceSum(input) {
for (let i = 0; i < input.length - 1; i ) {
input[i] = input[i 1];
}
console.log("input: " input);
if (input.length > 1)
{
//remove last item by reducing length of the array
input.length--;
return reduceSum(input);
}
//return final result or 0 if array is empty
return input[0] || 0;
}
console.log("result:", reduceSum([1, 2, 3, 4, 5]) == 48)
console.log("result:", reduceSum([1, 2, 3, 4]) == 20)
console.log("result:", reduceSum([5]) == 5)
console.log("result:", reduceSum([]) == 0)
console.log("result:", reduceSum([1, 3, 5]) == 12)
console.log("result:", reduceSum([-5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, -5, 5]) == 0)
console.log("result:", reduceSum([-5, 5, 5, -5]) == 20)