# How to sum up specific array elements?

How to sum up particular elements of an array that will equal a particular number.
For example,

Here’s an array [1, 5, 10, 20, 35, 40, 70, 90]

and the required number is 76.

Which means we need to add 70 + 5 + 1.

How do we determine those numbers and add them?

76 can be achieved by doing 40+35+1 as well or 40+20+10+5+1.

So, these are not the only numbers satisfying the condition.
Is there any specific constraint in algorithm?

Give more details about the algorithm in hand.

No, there can be any possibility of combination. There isn’t any further criteria.

So, what should the function return?

An array of the possible values that form the number.

No reply?? I am surprised that there are no proposed solutions to this.

I thought of the solution in seconds. However, this isn’t really an FCC problem. Is it homework? Also, you’ve had 3 days to work on this, and are relying solely on the brains of others? I am disinclined to help, but:

1 Like

Nope. I have been trying to solve the last Javascript project “Cash Register” and so far I am unable to make any logic for it.

Well, to pass the tests, you don’t need DFS. However, if you want to aim higher than the tests, you’ll need DFS to traverse a tree with literally one fork. Spoiler below:

In US currency, almost every denomination is a multiple of the unit smaller than it, except quarters and dimes (\$0.25 and \$0.10, respectively), so there are conditions under which you need to explore two possible ways to make change.

But where’d you get the problem about which this topic was written? This forum is mostly about FCC, but isn’t limited to that alone. My issue was the tone in which you said:

No reply?? I am surprised that there are no proposed solutions to this.

Expecting others to do the intellectual work for you implies that you are trying to pass off the work of others as your own. This may not be the case, but it sure seems like it. Prove my inference wrong, and I’ll gladly help.

1 Like

I made the problem up myself as an example to seek guidance from experts. I thought creating an example of it is the best way to ask how to do it. I usually don’t give up like that. I tried to solve it for 4 days and now I am seeking help because I am unable to do so.

I have been able to get this far though:

``````function checkCashRegister(price, cash, cid) {
var cidtotal = 0;
var cid2 = [];
var temp = [];
var real2 = [];

/* var real = [["PENNY", 0.01], ["NICKEL", 0.05], ["DIME", 0.1], ["QUARTER", 0.25], ["ONE", 1], ["FIVE", 5], ["TEN", 10], ["TWENTY", 20], ["ONE HUNDRED", 100]];
*/

var real = [0.01, 0.05, 0.1, 0.25, 1, 5, 10, 20, 100];

var change = cash - price;
console.log(change);

for (x = 0; x < cid.length; x++) {
cid2.push(cid[x][1]);
}
console.log(cid2);

cidtotal = cid2.reduce(function(item, total) {
return item + total;
}, 0);

console.log(cidtotal);

var real2 = real.slice();
console.log(real2);

if (change > cidtotal) {
return {"status" : "INSUFFICIENT_FUNDS", "change" : []};
}

else if (change == cidtotal) {
return {"status" : "CLOSED", "change" : cid};
}

else if (change < cidtotal) {
for (var i = real.length-1; i >= 0; i--) {
while (real[i] < (cid2[i] - real2[i])) {
real[i] = real[i] + real2[i];
}
temp.push(real[i]);
}

console.log(temp);
}

}

// Example cash-in-drawer array:
// [["PENNY", 1.01],
// ["NICKEL", 2.05],
// ["DIME", 3.1],
// ["QUARTER", 4.25],
// ["ONE", 90],
// ["FIVE", 55],
// ["TEN", 20],
// ["TWENTY", 60],
// ["ONE HUNDRED", 100]]

checkCashRegister(3.26, 100, [["PENNY", 1.01], ["NICKEL", 2.05], ["DIME", 3.1], ["QUARTER", 4.25], ["ONE", 90], ["FIVE", 55], ["TEN", 20], ["TWENTY", 60], ["ONE HUNDRED", 100]]);
``````

And my idea was to use the:

``````temp.push(real[i]);
``````

inside the while loop to include all possible values in an array and find out if any of those values can add up to match the change figure.

Okay. Well, you need to traverse the whole graph of “possible combinations.” If you take the tree structure in the Wikipedia as an example, you can conceptualize each node as an array made up of combinations of length 1 to n, where n==array.length. Each “layer” of the tree represents a different `combinationArray` length. You have to create each variant of `combinationArray` and test it for sum(combinationArray) == 76. That will be a complete DFS of the search tree. You don’t need to implement a tree to do this, just make sure your algorithm maps onto that conceptual tree traversal.

One optimization you can do is to run the tree traversal on a filtered sub-array of the initial input, removing all elements that are larger than 76 first.

Where does the 76 figure come from?

Okay, now I really don’t believe you:

How to sum up particular elements of an array that will equal a particular number.
For example,

Here’s an array [1, 5, 10, 20, 35, 40, 70, 90]

and the required number is 76.

Which means we need to add 70 + 5 + 1.

How do we determine those numbers and add them?

If it is to be solved without any performance consideration, you may find the sum by iterating through the array, take the value for the current index, and start summing it with the other values. You would have two cases, either the sum is greater than the value asked, which you don’t want, or it is equals, which you want. Now, how do you know which numbers were used? You can think about that

lol i was talking in context to my real problem now.

Can it be done with my existing code? Have you tried it yourself?

But are you actually trying to achieve what you first asked, or is it different?

This is what i got for that, without any elegant array function ):

``````const findSum = (array, value) => {
const summedValues = [];
let sum = 0;

for (let i = 0; i < array.length; i++) {
// Empty the array.
summedValues.splice(0, summedValues.length);

sum = array[i];
summedValues.push(array[i]);

for (let j = 0; j < array.length; j++) {
// Make sure not to use the initial value
if (j !== i) {
sum += array[j];
summedValues.push(array[j]);

if (sum === value) {
// Turns the array into a string and replaces
// spaces with ' + '
return summedValues.join(' ').replace(/\s/g, ' + ');
}

if (sum > value) {
break;
}
}
}
}
};
``````
2 Likes

Thanks for this. I will try to apply this logic to my real problem.