Friday, July 17, 2015

LeetCode OJ - Number of Digit One

Problem:

Please find the problem here.

Solution:

The problem is all about arranging the digits so that it is easy to count them, consider counting the number of '1' in 21.

The digits look like this

2
1
2
0
1
9
1
8
1
7
1
6
1
5
1
4
1
3
1
2
1
1
1
0
0
9
0
8
0
7
0
6
0
5
0
4
0
3
0
2
0
1
0
0


The key idea is to count these four region separately, although I used a two digits number, imagine the '2' is in fact '32', or any number with any number of digits.

It is trivial to count the number of '1' in a single digit number, so we will skip that and assume an implementation of countDigitOne() is available recursively.

The red part is simply the single digit problem, so we have the answer for that one.
The blue part is simply 0-9 repeated 2 times, so we can compute that as (21/10)
The yellow part is the key, and it is tricky. Let imagine the problem is 324 instead of 21. The yellow part would then consist of

31
.. 10 times ...
31
30
... 10 times ...
30
...
00

Since we are only doing counting, so we can shuffle them into a pattern we like

31
30
...
00
31
...
and the whole thing repeated 10 times.
00

That way, the yellow part is simple now, it is just countDigitOne(n/10 - 1) * 10

Last but not least, we need to solve the red part. The red part is simply the number of 1 in the MSBs * (n % 10 + 1) times. The number of 1 is the MSBs can be computed as countDigitOne(n/10) - countDigitOne(n/10 - 1).

So that's it, here is the code.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/number-of-digit-one/

#include "LEET_NUMBER_OF_DIGIT_ONE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_NUMBER_OF_DIGIT_ONE
{
    class Solution
    {
    public:
        int countDigitOne(int n)
        {
            if (n < 10)
            {
                return n >= 1 ? 1 : 0;
            }
            else
            {
                // 324  ++\
                // 323  ++\
                // 322  ++\
                // 321  ++\
                // 320  ++\
                //      **.
                //      **.

                int lsb = n % 10;
                int msbs = n / 10;

                int msbRepeatingUnitPart = countDigitOne(msbs - 1);
                int lsbRepeatingPart = msbs;                                                // This is the '.' part, 0-9   repeated 32 times
                int lsbResidue = countDigitOne(lsb);                                        // This is the '\' part, 0-4   repeated 1  times
                int msbsRepeatingPart = msbRepeatingUnitPart * 10;                          // This is the '*' part, 00-31 repeated 10 times
                int msbsResidue = (countDigitOne(msbs) - msbRepeatingUnitPart) * (lsb + 1); // This is the '+' part, 32    repeated 5  times

                return lsbRepeatingPart + lsbResidue + msbsRepeatingPart + msbsResidue;
            }
        }
    };
};

using namespace _LEET_NUMBER_OF_DIGIT_ONE;

int LEET_NUMBER_OF_DIGIT_ONE()
{
    Solution solution;
    for (int i = 1; i <= 50; i++)
    {
        cout << i << "\t" << solution.countDigitOne(i) << endl;
    }
    return 0;
}

No comments :

Post a Comment