This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:

Given n = 13,

Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

b'

\n## Solution

\n

\n#### Approach #1 Brute force [Time Limit Exceeded]

\n

\n#### Approach #2 Solve it mathematically [Accepted]

\n

\n

'
\n\n

\n\n

**Intuition**

Do as directed in question.

\n**Algorithm**

- \n
- Iterate over from to : \n
- Convert to string and count in each integer string \n
- Add count of in each string to the sum, say \n \n

**Complexity Analysis**

- \n
- Time complexity: . \n
- We iterate from to \n \n
- \n
In each iteration, we convert integer to string and count \'1\' in string which takes linear time in number of digits in , which is .

\n \n - \n
Space complexity: Extra space for the countr and the converted string .

\n \n

\n

**Intuition**

In Approach #1, we manually calculated the number of all the s in the digits, but this is very slow. Hence, we need a way to find a pattern in the way s (or for that matter any digit) appears in the numbers. We could then use the pattern to formulate the answer.

\nConsider the s in place , place, place and so on... An analysis\nhas been performed in the following figure.

\n\nFrom the figure, we can see that from digit \'1\' at place repeat in group of 1 after interval of . Similarly, \'1\' at place repeat in group of 10 after interval of .\nThis can be formulated as .

\nAlso, notice that if the digit at place is , then the number of terms with is increased by , if the number is say . As if digits at place is greater than , then all the occurances of numbers with at place have taken place, hence, we add .\nThis is formluated as .

\nLets take an example, say .

\nNo of in place = (corresponding to 1,11,21,...1221) + (corresponding to 1231) =\n

\nNo of in place = (corresponding to 10,11,12,...,110,111,...1919) +(corresponding to 1210,1211,...1219)=\n

\nNo of in place = (corresponding to 100,101,12,...,199) +(corresponding to 1100,1101...1199)=\n

\nNo of in place = +(corresponding to 1000,1001,...1234)=\n

\nTherefore, Total = .

\nHerein, one formula has been devised, but many other formulae can be devised for faster implementations, but the essence and complexity remains the same. The users are encouraged to try to divise their own version of solution using the mathematical concepts.

\n**Algorithm**

- \n
- Iterate over from to incrementing by each time: \n
- Add to representing the repetition of groups of $$i$ sizes after each interval. \n
- Add to representing the additional digits dependant on the digit in th place as described in intuition. \n

**Complexity analysis**

- \n
- Time complexity: . \n
- \n
No of iterations equal to the number of digits in n which is \n

\n \n - \n
Space complexity: space required.

\n \n

\n

Analysis written by @abhinavbansal0.

\n