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

• // 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;
}``````

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