233. Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

For example:
Given n = 13,
Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

Solution:

We count number of 1 by each digit positions. 

First let's consider ones position,

if n=115,

all 1 in ones position are: 1,11,21,31,41,51,61,71,81,91,101,111,121,131

Total amount 14 (we only consider 1 in ones positions) which is (135/10 +1)*1 .

Next let's consider 1 in tens positions: 10,11,12,13,14,15,16,17,18,19, 110,111,112,113,114,115 

Total count 16 : (115/100)* 10+15-10+1.

1 in hundreds positions: 100-115

total count 16, (115-100)+1.

Another example: Let's say n= 120,

Count 1 in tens positions: 10,11,12...18,19, 110,111,112,...118,119, total count is 20.

We can easily identify the pattern. 

Let's say count 1 in tens position, we set factor =10, and nextFactor=factor*10=100

int num=n/nextFactor;

int mod=n%nextFactor;

The count will be in the following 3 cases:

if (mod<factor)  the count = num*factor eg.109, count=10 : 10,11...18.19

if(mod>=factor*2) the count=(num+1)*factor eg.120, count= 20 : 10,11,...18,19, 110,111...118,119

if(mod>=factor && < factor*2) in between the count= num*factor+ mod-factor+1. eg. 115, count =16, 10,11....18,19,110,111,112,113,114,115.

We can do the same thing for all digits positions and sum up to get the total counts.

Code:

Use long to cover integer overflow.

 public int countDigitOne(int n) {  
     long factor=1;  
     int count=0;  
     while(n/factor!=0){  
       long com=factor*10;  
       long num=n/com;  
       long mod=n%com;  
       if(mod<factor) count+=num*factor;  
       else if(mod>=factor*2) count+=(num+1)*factor;  
       else count+=(num*factor)+mod-factor+1;  
       factor=com;  
     }  
     return count;  
   }