Scala algorithm: Compute single-digit sum of digits

Published

Algorithm goal

\(909\) sums to \(18\), which sums to \(9\).

Find the best way to compute it for any positive \(n\), efficiently.

Test cases in Scala

assert(sumOfDigits(0) == 0)
assert(sumOfDigits(2) == 2)
assert(sumOfDigits(8) == 8)
assert(sumOfDigits(10) == 1)
assert(sumOfDigits(16) == 7)
assert(sumOfDigits(32) == 5)
assert(sumOfDigits(64) == 1)
assert(sumOfDigits(101) == 2)
assert(sumOfDigits(109) == 1)
assert(sumOfDigits(128) == 2)
assert(sumOfDigits(256) == 4)
assert(sumOfDigits(512) == 8)
assert(sumOfDigits(999) == 9)
assert(sumOfDigits(1024) == 7)
assert(sumOfDigits(2048) == 5)
assert(sumOfDigits(4096) == 1)

Algorithm in Scala

4 lines of Scala (version 2.13), showing how concise Scala can be!

Get the full algorithm Scala algorithms logo, maze part, which looks quirky!

or

'Unlimited Scala Algorithms' gives you access to all the Scala Algorithms!

Upon purchase, you will be able to Register an account to access all the algorithms on multiple devices.

Stripe logo

Explanation

This involves a bit of mathematics to figure out - but we can get an \(O(1)\) solution here:

The sum of digits of sum of digits... is equal to that digit modulo 9; if we take a number that is composed of digits\(abcd\), which equals \(10^3 \times a + 10 ^ 2 \times b + 10 \times c + d\), and then using %/modulo 9 we get:\(a + b + c + d (\mod 9)\), which is also \(((a + b) (\mod 9) + (c + d) (\mod 9))(\mod 9)\). Combining with a modulo table, you will notice thatindeed for example \(8 + 7 = 15\), and applying modulo 9 on \(15\) gives us \(6\), which is precisely the sum of digits \(1\) and \(5\). (this is © from www.scala-algorithms.com)

View the rest of Scala algorithms