4

What is the algorithm to calculate the cross sum (516 = 5 + 1 + 6 = 12) with just a while loop, add, subtract, divide and mulitply? I would use the modolus but I don't know how to replicate it with just the basic mathematical terms I mentioned.

das
  • 63
  • 1
  • 8
  • 3
    This notion may help: `a mod b` = `a - ((a div b) * b)`. – Gassa Mar 09 '17 at 17:58
  • somewhat of a duplicated for [this question](http://stackoverflow.com/questions/27096670/how-to-sum-digits-of-an-integer-in-java) – KillerPollo Mar 09 '17 at 18:01
  • Possible duplicate of [How to sum digits of an integer in java?](http://stackoverflow.com/questions/27096670/how-to-sum-digits-of-an-integer-in-java) – Paul Hankin Mar 09 '17 at 18:47
  • This is called the `digital-sum` I believe or maybe `digital-root` can't remember. Anyways there is a super simple formula with modulo on wikipedia if I recall, no loop needed. – Albert Renshaw Mar 09 '17 at 18:51
  • 1
    Is the allowed "divide" an integer division--i.e. is it `div` or `//` rather than `/` (the latter two in Python 3)? – Rory Daulton Mar 09 '17 at 19:30

2 Answers2

1

Let's assume that by division, you mean float-division; otherwise you could write your own mod operation using floor-division.

Here's an O(n) time, O(1) space algorithm using loops and comparisons to enumerate the digits and sum them (where n is the number of digits).

JavaScript code:

function crossSum(num){
  // Find the largest power of ten and number of digits, O(n)
  var power = 1,
      numDigits = 1;
      
  while (power * 10 <= num){
    power = power * 10;
    numDigits++;
  }
  
  // Calculate cross sum, O(constant * n) = O(n)
  var sum = 0,
      digit;
  
  while (num > 0){
    digit = 0;
    
    while ((digit + 1) * power <= num)
      digit++;
      
    console.log(digit)
    sum = sum + digit;
    num = num - power * digit;
    power = power / 10;
  }
  
  return sum;
}

console.log(crossSum(516));
גלעד ברקן
  • 23,602
  • 3
  • 25
  • 61
-1

Digital Sum

The formula requires no looping and is lifted from the Wikipedia page on Digital Sum

enter image description here

This of course uses exponents and modulo which is not one of your listed operands but that limitation is something that would never exist in any modern day programming language, which leads me to believe its not a real limitation or this is a home work problem. In any event, StackOverflow is here as a reference for future programmers to find ways to solve problems and I believe this is the solution to digital-sum problem for all intents and purposes so I'm listing it here for future readers. You do not have to accept this answer as it is not a real answer but more a reference for others.

Community
  • 1
  • 1
Albert Renshaw
  • 17,282
  • 18
  • 107
  • 195