@@ -0,0 +1,2289 @@
+/*%0AGiven an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.%0A%0AFor example:%0AGiven n = 13,%0AReturn 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.%0A%0AHint:%0A%0A    Beware of overflow.%0A%0A*/%0A%0Aimport java.io.*;%0Aimport java.util.*;%0A%0Apublic class NumberofDigitOne %7B%0A%09public static int countDigitOne(int n) %7B%0A        if(n %3C=0 ) return 0;%0A        if(n %3C 10) return 1;%0A        List%3CInteger%3E digit = new ArrayList%3CInteger%3E();%0A%09%09int k = n;%0A        while(k %3E= 10)%7B%0A            int bit = k%2510;%0A            digit.add(bit);%0A            k = k/10;%0A        %7D%0A        digit.add(k);%0A        int counts = 0;%0A        int mod = 1;%0A        for(int i = 0; i %3C digit.size(); i++)%7B%0A            int bit = digit.get(i);%0A            int front = n/(mod*10);%0A            int after = n%25mod;%0A%09%09%09System.out.print(%22bit: %22 + bit + %22 front:%22 + front + %22 after:%22 + after);%0A%09%09%09System.out.println();%0A            if(bit==0)%7B%0A                counts += front * mod;%0A            %7Delse if(bit==1)%7B%0A                counts += front*mod + after + 1;%0A            %7Delse if(bit%3E1)%7B%0A                counts += (front+1) * mod;%0A            %7D%0A            mod *=10;%0A        %7D%0A        return counts;%0A    %7D%09%0A%0A%09public static int countDigitOneOverFlow(int n) %7B%0A        if(n %3C=0 ) return 0;%0A        if(n %3C 10) return 1;%0A        List%3CInteger%3E digit = new ArrayList%3CInteger%3E();%0A%09%09int k = n;%0A        while(k %3E= 10)%7B%0A            int bit = k%2510;%0A            digit.add(bit);%0A            k = k/10;%0A        %7D%0A        digit.add(k);%0A        long counts = 0;%0A        long mod = 1;%0A        for(int i = 0; i %3C digit.size(); i++)%7B%0A            int bit = digit.get(i);%0A            long front = n/(mod*10);%0A            long after = n%25mod;%0A            if(bit==0)%7B%0A                counts += front * mod;%0A            %7Delse if(bit==1)%7B%0A                counts += front*mod + after + 1;%0A            %7Delse if(bit%3E1)%7B%0A                counts += (front+1) * mod;%0A            %7D%0A            mod *=10;%0A        %7D%0A        return (int)counts;%0A    %7D%09%0A%09%0A%09public static void main(String%5B%5D args) %7B%0A%09%09Scanner reader = new Scanner(System.in); %0A%09%09System.out.println(%22Enter a number: %22);%0A%09%09int n = reader.nextInt();%0A%09%09int res = countDigitOne(n);%0A%09%09System.out.println(%22number of digit one: %22 + res);%0A%09%09return;%0A%09%7D%09%0A%7D%0A

number of digit one