Search code examples
loopsmathtime-complexityc++17

Optimize the Sum of Digits of N

Codewars Question: (Sum of Digits / Digital Root)

Given n, take the sum of the digits of n. If that value has more than one digit, continue reducing in this way until a single-digit number is produced. The input will be a non-negative integer.

Test Cases:

16  -->  1 + 6 = 7
942  -->  9 + 4 + 2 = 15  -->  1 + 5 = 6
132189  -->  1 + 3 + 2 + 1 + 8 + 9 = 24  -->  2 + 4 = 6
493193  -->  4 + 9 + 3 + 1 + 9 + 3 = 29  -->  2 + 9 = 11  -->  1 + 1 = 2

My code:

#include <bits/stdc++.h>
using namespace std;

int singleDigit(int n)
{
   int ans;
   while (n > 0)
   {
      int lastDigit = n % 10;
      n /= 10;

      ans += lastDigit;
   }

   while (ans > 9)
   {
      int n1 = ans;
      ans = 0;
      while (n1 > 0)
      {
          int lastDigit = n1 % 10;
          n1 /= 10;

          ans += lastDigit;
      }
   }

   return ans;
}

int main()
{
    cout << singleDigit(49319366) << endl;

    return 0;
}

Is there a better or optimized way to solve this problem or to reduce time complexity?

Solution

  • This function works for non-negative integers, adapting for negative numbers is straightforward.

    int singleDigit(int n) 
{
    return (n-1) % 9 + 1;
}

    It has the following advantages:

    • no variables to forget to initialise
    • no loops to commit an off-by-one error
    • fast

    The disadvantages are:

    • it is not immediately clear how or why it works

    For more information on the last bullet point, see: