CODEWITHSUNDEEP
loopsmathtime-complexityc++17
Jay1105
Jay1105

Reputation: 80

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?

Upvotes: 2

Views: 675

Answers (2)

Vineet Kumar Gupta
Vineet Kumar Gupta

Reputation: 535

Here is the code with o(1) Time and Space Complexity to find the sum of digits.

It's based on the property that "A number is divisible by 9 if the sum of its digits is divisible by 9."

int AddDigits(int num) {
  if (num == 0) {
    return 0;
  } else {
    return (num - 1) % 9 + 1;
  }
}

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119857

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:

Upvotes: 1

Related Questions