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.

The idea is to calculate occurrence of 1 on every digit. There are 3 scenarios, for example

if n = xyzdabc
and we are considering the occurrence of one on thousand, it should be:

(1) xyz * 1000                     if d == 0
(2) xyz * 1000 + abc + 1           if d == 1
(3) xyz * 1000 + 1000              if d > 1

iterate through all digits and sum them all will give the final answer

Source

The way of extracting the pattern of this problem is so fuzzy.

Tips: problems related to math always require a formula like solution and needs to divide the problem by each digit, and then resolve by using recursion or iteration

class Solution {
    public int countDigitOne(int n) {
        if(n<=0) return 0;
        int res = 0,digit=1,x=n;
        while(x>0){
            int d=x%10;
            if(d>1) res+=digit;
            if(d==1) res += n%digit+1;
            x/=10;
            res+=x*digit;
            digit*=10;
        }
        return res;
    }
}