Approach #1 Brute force [Time Limit Exceeded]
Do as directed in question.
- Iterate over from to :
- Convert to string and count in each integer string
- Add count of in each string to the sum, say
- Time complexity: .
- We iterate from to
In each iteration, we convert integer to string and count '1' in string which takes linear time in number of digits in , which is .
Space complexity: Extra space for the countr and the converted string .
Approach #2 Solve it mathematically [Accepted]
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.
Consider the s in place , place, place and so on... An analysis has been performed in the following figure.
From 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 . This can be formulated as .
Also, 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 . This is formluated as .
Lets take an example, say .
No of in place = (corresponding to 1,11,21,...1221) + (corresponding to 1231) =
No of in place = (corresponding to 10,11,12,...,110,111,...1919) +(corresponding to 1210,1211,...1219)=
No of in place = (corresponding to 100,101,12,...,199) +(corresponding to 1100,1101...1199)=
No of in place = +(corresponding to 1000,1001,...1234)=
Therefore, Total = .
Herein, 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.
- Iterate over from to incrementing by each time:
- Add to representing the repetition of groups of $$i$ sizes after each interval.
- Add to representing the additional digits dependant on the digit in th place as described in intuition.
- Time complexity: .
No of iterations equal to the number of digits in n which is
Space complexity: space required.
Analysis written by @abhinavbansal0.