My Straight Forward Recursion Solution


  • 0
    K
    public int countDigitOne(int n) {
        if (n < 100)
            return countUnderOneHundred(n);
        //Locate the most significant digit
        long mod = 1;
        while ((long)n >= mod * 10) {
            mod *= 10;
        }
        if (n/(int)mod == 1) {
            //for example, 1032 contains 1s for 999 + 1s for 32 + 33 most significant digit 1s
            return (n/(int)mod)*countDigitOne((int)mod-1) + countDigitOne(n%(int)mod) + n%(int)mod + 1;
        } else {
           //for example, 2032 contains 1s for two 999 + 1s for 32 + 1000 most significant digit 1s
            return (n/(int)mod)*countDigitOne((int)mod-1) + countDigitOne(n%(int)mod) + (int)mod;
        }
    }
    
    private int countUnderOneHundred(int num) {
        if (num <= 0)
            return 0;
        if (num >= 1 && num < 10)
            return 1;
        if (num == 10)
            return 2;
        if (num == 11)
            return 4;
        if (num < 20)
            return num%10 + 3;
        return 12 + (num-11)/10;
    }

Log in to reply
 

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