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

Example: 

Input: 15
Output: 9
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13, 14 and 15.

Approach: Let's start with a simpler problem: how many digits 1 appearing in all non-negative integers less than or equal to maximum of n-digits length integer?  In other words, how many "1"s in  0-9 (1 digit), how many "1"s in 0-99(2 digits), how many "1"s in 0-999 (3 digits) and so on. 

• From 0-9, it is easy to find out there is only one "1", it appeared in integer 1.

• From 0-99, count of "1" can be obtained as follows:
• Consider two blank slots in which we will fill the numbers: [ ][ ], both slots can take any 1 digit value i.e. 0 to 9. We can denote it as [0-9][0-9]. 
• Here there are 2 cases which are [0, 2-9][0-9] and [1][0-9]
• Case 1 - [0, 2-9][0-9]: There is no "1" in the left digit. "1" only appears in the right digit, here is only one "1" in [0-9](We have already calculated that 0-9 has only 1 "1") so for each number in [0, 2-9], we have "1" at its lowest digit. We have 9 different possible highest digits, i.e., 0,2,3,4,5,6,7,8,9, for every one of them, the lowest digit can generate only 1 "1", in total there will be 9 *1 = 9  "1"s in this case.
• Case 2 - [1][0-9]: "1" is at highest digit, which means every possible number in its lower digits (now is [0-9]) contains one "1" so there are 1*10  = 10 "1"s in this case but we are missing one case of "11" where 1 will be on lowest digit too so there will be 11 "1"s in this case. We can also think [0-9] will also give one "1".
• Sum of case 1 and case 2 is 20 so there will be 20 "1"s in (0-99).

• From 0-999, count of "1" can be obtained as follows:
• Three slots: [][][] with 2 cases [1][0-9][0-9] and [0, 2-9][0-9][0-9]
• Case 1 - [0, 2-9][0-9][0-9]: We have calculated number of 1s [0-9][0-9] already and there will be no 1 at highest digit in this case so total number of "1"s are 9 * 20 = 180 in this case.
• Case 2 - [1][0-9][0-9]: Here at the highest digit there will be always "1" so number of 1s are 100-199 i.e. 100 and [0-9][0-9] will produce 20 more "1'"s which we have pre-calculated so total number of "1" are 120 in this case.
• Sum of case 1 and case 2 is 300 so there will be 300 "1"s in (0-999).

So now if you look closely, you will find a pattern here:

Total_Number_Of_1s(n) = 9 * Total_Number_Of_1s(n - 1) + 10 ^ (n - 1) + Total_Number_Of_1s(n - 1)

Total_Number_Of_1s(n) = 10 * Total_Number_Of_1s(n - 1) +  10 ^(n-1)

where n is equal to number of digit and Total_Number_Of_1s(1) = 1. 

This is all good but it just solve the problem for specific ranges like 0-9 or 0-99 or 0-999 and so on. How to solve this problem for something like 0-n. Let's take an example of n = 2746 and solve it, we will use approximately same strategy here too:  

Total_Number_Of_1s_Random(2746) = Total_Number_Of_1s_Random(0-999) +  Total_Number_Of_1s_Random(1000-2746)

= Total_Number_Of_1s(3) + Total_Number_Of_1s_Random(1000-2746)

= Total_Number_Of_1s(3) +  1000 + Total_Number_Of_1s(3) + Total_Number_Of_1s_Random(2000-2746)

# Number of 1s in 1000 to 1999 will be 1000 (All highest digits will have 1) + Total_Number_Of_1s(3) (number of 1s in 0-999)

= 2 * Total_Number_Of_1s(3) + 1000 + Total_Number_Of_1s_Random(2000-2746)

= 2 * Total_Number_Of_1s(3) + 1000 + Total_Number_Of_1s_Random(0-746) 

# We can ignore highest digit as it will be always 2

= 2 * Total_Number_Of_1s(3) + 1000 + Total_Number_Of_1s(2) + Total_Number_Of_1s_Random(100-746)

= 2 * Total_Number_Of_1s(3) + 1000 + Total_Number_Of_1s(2) + 100 + Total_Number_Of_1s(2) + Total_Number_Of_1s_Random(200-746)

=  2 * Total_Number_Of_1s(3) + 1000 + 2 * Total_Number_Of_1s(2) + 100 + Total_Number_Of_1s_Random(200-746)

= 2 * Total_Number_Of_1s(3) + 1000 + 7 * Total_Number_Of_1s(2) + 100 + Total_Number_Of_1s_Random(0-46)

# For each 2xx, 3xx, 4xx, .. 6xx, we will add more to Total_Number_Of_1s(2) (0-99)

= 2 * Total_Number_Of_1s(3) + 1000 + 7 * Total_Number_Of_1s(2) + 100 + Total_Number_Of_1s(1)  + Total_Number_Of_1s_Random(10-46)

= 2 * Total_Number_Of_1s(3) + 1000 + 7 * Total_Number_Of_1s(2) + 100 + 2 * Total_Number_Of_1s(1)  + 10 + Total_Number_Of_1s_Random(20-46)

= 2 * Total_Number_Of_1s(3) + 1000 + 7 * Total_Number_Of_1s(2) + 100 + 4 * Total_Number_Of_1s(1)  + 10 + Total_Number_Of_1s_Random(40-46)

= 2 * Total_Number_Of_1s(3) + 1000 + 7 * Total_Number_Of_1s(2) + 100 + 4 * Total_Number_Of_1s(1)  + 10 + Total_Number_Of_1s_Random(0-6)

= 2 * 300 + 1000 + 7 * 20 + 100 + 4 * 1 + 10 + 1

= 1855

Hopefully after running through this example the strategy is clear. Basically we go from lowest digit to highest and follow the following steps:

1. If current digit is 0. Nothing to be added.
2. If current digit is 1, we add current_digit * Total_Number_Of_1s(position  - 1), number formed lower digits and 1(for 125 => 25 + 1(for 100)).
3. If current digit is > 1, then we add current_digit * Total_Number_Of_1s(position - 1) and 10 ^ position

* Here position current digit's position from left to right 

Implementation in C#:

        public static int CountDigitOne(int n)

        {

            int result = 0;

            long memory = 0;

            for (long i = 1; i <= n; i = i * 10)

            {

                long d = n % (i * 10) / i; //get the current digit

                result += (int)(d * memory + (d == 1 ? 1 : 0) * (n % i + 1) + (d > 1 ? 1 : 0) * (i));

                memory = memory  * 10 + i; // i here is 10 ^ (digits - 1)

            }

            return result;

        }

Complexity: O(logn)