Leetcode 233 (Number of Digit One) was fun.

This one is a math problem. And I enjoyed every bit of cracking the equation. The problem was, “Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.”

At first I thought of doing recursion. But as I was drafting for recursion I found a common pattern, and in stead figured out equation to find out the result. It took me almost 3 hours to devise the solution and 1 hour more to implement into code. And It was successful in the end. The solution executed in 0ms with O(n) complexity where n is the length of the input number or the number of digits in the input number.

Here’s a an overview of the solution:
We can divide all digits into three categories. 0, 1, higher then 1. If we have a value higher than one like 6756. Then, there must be 1000 number of 1s + the number of 1s appearing between 1 to 6000. Now, within each 1000 digits (0-999, 1000-1999, ...) the number of 1s appearing can be determined in the similar manner. That makes:

leftmost digit range = powerLevel + (digit \ (10 ^ (powerLevel -1)) * powerLevel);

difficulty rises when digit = 1. That time the equation becomes like this,leftmost digit range = (10 ^ (powerLevel - 1)* powerLevel) + remaining numbers + 1;

For, digit = 0, we can ignore calculation. As for 2084. if we have calculated 0-2000, and we'll calculate 0-84 and 0-4. then, there is no need to add the 0 into calculation.
Additional case is when powerLevel becomes zero, the powerLevel-1 becomes -1. So, we return 1.

A more detailed version with example can be found in the solution provided in my leetcode solution. Feel free to have a look.