Thread: Total sum of digits

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    43

    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?

  2. #2
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Say what?
    Mainframe assembler programmer by trade. C coder when I can.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    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.

  4. #4
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    This is a common programming contest problem. You can probably find the solution somewhere, if you want.

    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.

  5. #5
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    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.

  6. #6
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    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.

  7. #7
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    You can do this iteratively, too, but it won't be any faster, and the code will be more awkward.

  8. #8
    Registered User
    Join Date
    Apr 2010
    Posts
    43
    I understand the situation. Thank you very much!

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    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 . . . .
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Simple Restaurant Point-of-Sale Application: Help?!
    By matt.s in forum C Programming
    Replies: 14
    Last Post: 04-16-2010, 05:36 PM
  2. How can i count sum of digits in odd/even places?
    By cowa in forum C Programming
    Replies: 9
    Last Post: 11-16-2009, 11:43 PM
  3. Replies: 8
    Last Post: 11-03-2008, 09:48 PM
  4. The Timing is incorret
    By Drew in forum C++ Programming
    Replies: 5
    Last Post: 08-28-2003, 04:57 PM
  5. Replies: 4
    Last Post: 04-22-2003, 12:52 PM