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
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 09 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:
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 09 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/numberofdigitone/ #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, 09 repeated 32 times int lsbResidue = countDigitOne(lsb); // This is the '\' part, 04 repeated 1 times int msbsRepeatingPart = msbRepeatingUnitPart * 10; // This is the '*' part, 0031 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