online advertising

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"

// https://leetcode.com/problems/add-digits/

#include "LEET_ADD_DIGITS.h"
#include <map>
#include <iostream>
#include <vector>

using namespace std;

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

using namespace _LEET_ADD_DIGITS;

int LEET_ADD_DIGITS()
{
    NaiveSolution n;
    Solution s;
    for (int i = 0; i < 100000; i++)
    {
        if (s.addDigits(i) - n.addDigits(i) != 0)
        {
            cout << "Fail" << endl;
        }
    }
    return 0;
}

No comments :

Post a Comment