An other solution using the combine math


  • 0
    B

    For example, if n = 91,we count the 1 for every place。Consider the first one like “X1”,X may range from 0 to 9, so the ans += 10。Then the second one like “1X”,X may range from 0 to 9,and ans += 10;So the ans = 20。

    And what if n = 90, Consider "X1", X range from 0 to 9? No, When X = 9, The number is larger than n. So when we consider the current place, we need consider the original digital in the place. Notice that the original digital in the first place is 0. So,we can't get all the combine of the digital higher. We need to left one.

    To easy understand, I will change n value. Let n = 10197.

    • XXXX1 -----> 1019 + 1 (the combiner number of XXXX)
    • XXX1X -----> (101 + 1 )* 10 ( times 10 because the low place can range 0 to 9)
    • XX1XX -----> 10 * 100 + 97+1 ( notice the original digital is 1, so the higher place can't not be 18, because if higher place equals 18, the result string will be 181XX, and XX may be 99 or 98, will larger than 18197, so we let the higher digital range from 00 to 17, and plus the remainder 18100,18101...18197)
    • X1XXX -----> 1*1000 (it's similar to the 3 situation.)
    • 1XXXX ----->197+1

    There is the code

    public class Solution {
    public static void main(String[] args){
    	Solution sol = new Solution();
    	System.out.println(sol.countDigitOne(10197));
    }
    public int countDigitOne(int n) {
    	if( n <= 0) return 0;
        List<Integer> res = new ArrayList<Integer>();
        while( n != 0){
        	res.add(n%10);
        	n /= 10;
        }
        int ans = 0;
        for(int i = 0; i < res.size(); ++i){
        	int tmp = 0;
        	for(int j = res.size()-1; j > i; --j){
        		tmp += res.get(j)*Math.pow(10, j-i-1);
        	}
        	++tmp;
        	if(res.get(i) <= 1)
        		--tmp;
        	for(int j = i-1; j>-1; --j)
        		tmp *= 10;
        	if(res.get(i) == 1){
        		for(int j = i-1; j>-1; --j){
        			tmp += res.get(j)*Math.pow(10, j);
        		}
        		++tmp;
        	}
        	ans += tmp;
        }
        return ans;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.