package leetcode;

/**
 * https://leetcode.com/problems/number-of-digit-one/
 */
public class Problem233 {
    public int countDigitOne(int n) {
        if (n <= 0)
            return 0;
        if (n < 10)
            return 1;
        System.out.println("n="+ n);
        int t = (n % 10 + 1) * countDigitOne2(new Integer(n / 10).toString());
        if (n % 10 >= 1) {
            return countDigitOne(n / 10 - 1) * 10 + (n / 10 + 1) + t;
        } else {
            return countDigitOne(n / 10 - 1) * 10 + n / 10 + t;
        }
        
//        int result = 0;
//        for (int i = 1; i <= n; i *= 10) {
//            int j = n / i;
//            System.out.println(j);
//        }
//        return result;
//        
//        int result = 0;
//        for (int i = 1; i <= n; i++) {
//            int digit = countDigit(i);
//            int tmp = i;
//            for (int d = digit-1; d >= 0; d--) {
//                int divisor = (int) Math.pow(10, d);
//                int a = tmp / divisor;
//                if (a == 1) {
//                    result++;
//                }
//                tmp = tmp % divisor;
//            }
//        }
//        return result;
    }

    private int countDigit(int n) {
        int tmp = n;
        int digit = 0;
        while (tmp != 0) {
            digit++;
            tmp = tmp / 10;
        }
        return digit;
    }
    
    public static int countDigitOne2(String s) {
        int res = 0; 
        char[] arry = s.toCharArray();
        for(char c : arry) {
            if(c == '1') {
                res += 1;
            }
        }
        return res;
    }
    
    public static void main(String[] args) {
        Problem233 prob = new Problem233();
//        System.out.println(prob.countDigitOne(100)); // 21
//        System.out.println(prob.countDigitOne(1000)); // 301
//        System.out.println(prob.countDigitOne(10000)); // 4001
        System.out.println(prob.countDigitOne(1811)); // 1376
//        System.out.println(prob.countDigitOne(181)); // 121
//        System.out.println(prob.countDigitOne(121)); // 55
//        System.out.println(prob.countDigitOne(12341)); // 8117
//        System.out.println(prob.countDigitOne(13)); // 6
//        System.out.println(prob.countDigitOne(824883294)); // 767944060
    }
}

@@ -157,16 +157,18 @@
 (n %3C= 0)
+ %7B
 %0A       
@@ -178,24 +178,34 @@
   return 0;%0A
+        %7D%0A
         if (
@@ -211,16 +211,18 @@
 (n %3C 10)
+ %7B
 %0A       
@@ -248,35 +248,46 @@
     
-System.out.println(%22n=%22+ n)
+%7D%0A        int remainder = (n %25 10) + 1
 ;%0A  
@@ -304,20 +304,17 @@
 t = 
-(n %25 10 + 1)
+remainder
  * c
@@ -329,29 +329,16 @@
 tOne
-2(new 
+(
 Integer
-(n / 10)
 .toS
@@ -343,16 +343,22 @@
 oString(
+n / 10
 ));%0A    
@@ -549,861 +549,10 @@
     
-    %0A//        int result = 0;%0A//        for (int i = 1; i %3C= n; i *= 10) %7B%0A//            int j = n / i;%0A//            System.out.println(j);%0A//        %7D%0A//        return result;%0A//        %0A//        int result = 0;%0A//        for (int i = 1; i %3C= n; i++) %7B%0A//            int digit = countDigit(i);%0A//            int tmp = i;%0A//            for (int d = digit-1; d %3E= 0; d--) %7B%0A//                int divisor = (int) Math.pow(10, d);%0A//                int a = tmp / divisor;%0A//                if (a == 1) %7B%0A//                    result++;%0A//                %7D%0A//                tmp = tmp %25 divisor;%0A//            %7D%0A//        %7D%0A//        return result;%0A    %7D%0A%0A    private int countDigit(int n) %7B%0A        int tmp = n;%0A        int digit = 0;%0A        while (tmp != 0) %7B%0A            digit++;%0A            tmp = tmp / 10;%0A        %7D%0A        return digit;%0A    %7D%0A    
+%7D%0A
 %0A   
@@ -583,17 +583,16 @@
 DigitOne
-2
 (String 
@@ -612,39 +612,40 @@
 int 
-res
+count
  = 0;
- 
 %0A
+ 
        
- char%5B%5D arry =
+for (char c :
  s.t
@@ -660,35 +660,8 @@
 ay()
-;%0A        for(char c : arry
 ) %7B%0A
@@ -674,16 +674,17 @@
       if
+ 
 (c == '1
@@ -708,733 +708,65 @@
     
-res += 1;%0A            %7D%0A        %7D%0A        return res;%0A    %7D%0A    %0A    public static void main(String%5B%5D args) %7B%0A        Problem233 prob = new Problem233();%0A//        System.out.println(prob.countDigitOne(100)); // 21%0A//        System.out.println(prob.countDigitOne(1000)); // 301%0A//        System.out.println(prob.countDigitOne(10000)); // 4001%0A        System.out.println(prob.countDigitOne(1811)); // 1376%0A//        System.out.println(prob.countDigitOne(181)); // 121%0A//        System.out.println(prob.countDigitOne(121)); // 55%0A//        System.out.println(prob.countDigitOne(12341)); // 8117%0A//        System.out.println(prob.countDigitOne(13)); // 6%0A//        System.out.println(prob.countDigitOne(824883294)); // 767944060
+count += 1;%0A            %7D%0A        %7D%0A        return count;
 %0A   

Solve problem 233 (not my algorithm)