Total sum of digits

I am being asked to calculate the sum of digits , which will be obtained into an array. The problem is that I need to save both time and space.

My plan was to add each digit to the sum and verify if it's larger than 10. If it is, then I substract 10 out of it. But this also requires too much time... more than even recursivity. Ialso don't want to create other arrays...

Any ideas?

Say what?

Ok, sorry... so I have the number 1784. And I have to obtain the digits of the number in a vector. So the vector will contain :
1 7 8 4

Now I have to compute the sum of the digits... but that's not enough. I have to sum it until the result is less than 9.
So 1 + 7 + 8 + 4 is 20. And the answer is 2, because 2 + 0 = 2. This is what I want.

This is a common programming contest problem. You can probably find the solution somewhere, if you want.

Quote:

---

If it is, then I substract 10 out of it.

---

Huh? How does that work?

If you get 20, you want to make it 10? What if it's 31598325?

I don't THINK the number can ever grow, because
1999 >> 1+9+9+9 (worst case)

I would just do it recursively (or iteratively, same thing). Not sure if it can get into infinite recursion. In which case, you'll need a set to keep track of numbers you've already searched.

I understand that was very, very bad... So isn't it another way? I could not find any other solution and I would do my best to avoid recursion, as that is never recommended, because of the time it takes.

Recursion is not fundamentally any slower than anything else.

Many programming contest (and real life) problems can only be solved (or most naturally solved) using recursion.

Sure, you can write very slow code using recursion, but so can you with any other construct.

You can do this iteratively, too, but it won't be any faster, and the code will be more awkward.

I understand the situation. Thank you very much!

That said...

Quote:

---

Originally Posted by Veneficvs

My plan was to add each digit to the sum and verify if it's larger than 10. If it is, then I substract 10 out of it.

---

I believe that a correct amendment to your idea is to add the two digits of the intermediate sum if it is greater than 9, rather than subtracting 10 from the sum. After that addition, you continue the iteration with the result as the new sum.

I'm not sure I understood your suggestion for an algorithm correctly, laserlight. I interpreted it to mean something like this:

• Take the next digit and add it to the sum.
• If the sum exceeds 9, add the two digits together and replace the sum with this new number.
• Repeat until out of digits.

But of course this doesn't work, because the weighting of the digits you're adding changes every time your sum exceeds 9 . . . .

Code:

---

long winded method: 3958
    3+9+5+8 = 25
    2+5 = 7

iterative method: 3958
    3+9 = 12 -> 1+2 = 3
        3+5 = 8
            8+8 = 16 -> 1+6 = 7

---

Quote:

---

Originally Posted by dwks

I interpreted it to mean something like this:

---

Yes.

Quote:

---

Originally Posted by dwks

But of course this doesn't work, because the weighting of the digits you're adding changes every time your sum exceeds 9 . . . .

---

I relied on intuition rather than proof, so I could be wrong, but I note that your example is not a counterexample.

Hmm, you're right that my example isn't a counter example, and the more I try it the more I'm convinced your algorithm is correct. :) Your intuition is obviously better than mine . . . .