2

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?

Jay1105
  • 80
  • 6
  • Why do you need the first while loop? – Conor Jun 02 '21 at 09:35
  • @Conor - I'm using the first while loop just to take out the last digits and add it in answer, but for some test cases, I'm receiving a two-digit ans, which is against the expected output. So I'm putting one more while loop that will run till the ans becomes less than 9, so i will receive a single-digit output. But because of that, my time complexity is increasing. – Jay1105 Jun 02 '21 at 09:39
  • @n. 'pronouns' m. Yes, I know, that it is a basic Maths question, but I'm a beginner and I don't know how to implement it in a loop, or what will be the loop's condition and all. I tried but still getting a bad time complexity. Can you please send me the code? – Jay1105 Jun 02 '21 at 09:49

1 Answers1

1

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:

n. m. could be an AI
  • 112,515
  • 14
  • 128
  • 243