## Sunday, August 16, 2015

### LeetCode OJ - Add Digits

Problem:

Please find the problem here.

Solution:

Notice two things.

1. Sum of digits mod 9 = number mod 9 (quick proof: write the number as a sum of multiple of 10's power, push mod 9 into the sum and product)
2. The sum of digit function is never 0 except for 0.
So we can simply output the number mod 9 if it is not exactly divisible by 9, otherwise, output 9, except when the input is 0 then output 0.

Code:

#include "stdafx.h"

#include <map>
#include <iostream>
#include <vector>

using namespace std;

{
class NaiveSolution {
public:
{
int sum = 0;
while (num > 0)
{
sum += num % 10;
num = num / 10;
}
if (sum > 9)
{
}
else
{
return sum;
}
}
};
class Solution {
public:
{
if (num == 0)
{
return 0;
}
else
{
return (num - 1) % 9 + 1;
}
}
};
};

{
NaiveSolution n;
Solution s;
for (int i = 0; i < 100000; i++)
{
}