Dynamic Program Perspective to solve this problem in O(numberLength)


  • 0
    F

    // let length is the n's bit length, base is digit in the highest bit, restNumber is the number exclude highest bit,
    // the countDigitOne can be gotten by following formula.
    // (1) if base == 0, the digit one number is countDigitOne(restNumber)
    // (2) if base == 1, the digit one number is countDigitOne(restNumber) + pow(10, length-2)(length-1)base + (restNumber+1);
    // (3) if base > 1, the digit one number is countDigitOne(restNumber) + pow(10, length-2)(length-1)base+pow(10, length-1);
    // This formula can be executed by Dynamic Program. As next round's countDigitOne only depends on current round's countDigitOne, only using following variables can support this Dynamic Problem:
    // (1) pow: is for pow(10, length-2)
    // (2) base: keep current digit in highest bit
    // (3) count: keep current round countDigitOne
    // (4) restNumber: keep current round's rest number
    Initial Values:
    length = 2
    count = n%10 > 0 ? 1 : 0;
    pow = 1; Math.power(10, length-2);
    base = n%10;

        public int countDigitOne(int n) {
            if (n <= 0) return 0;
            if (n <= 9) return 1;
            int count = n%10 > 0 ? 1 : 0;
            int pow = 1;
            int base = n%10;
            int length = 2;
            int restNumber = n%10;
            while (n >= 10) {
                base = (n/10)%10;
                if (base == 1) count = count + pow*(length-1)*base + (restNumber+1);
                if (base > 1) count = count + pow*((length-1)*base + 10);
                n /= 10;
                pow *= 10;
                length++;
                restNumber += base*pow;
            }
            return count;
        }

Log in to reply
 

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