Leetcode: 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.

Hint:

Beware of overflow.

this one is the same with Lintcode: Digit Counts, 小心溢出，所以用了long型

当某一位的数字小于i时，那么该位出现i的次数为：更高位数字x当前位数
当某一位的数字等于i时，那么该位出现i的次数为：更高位数字x当前位数+低位数字+1
当某一位的数字大于i时，那么该位出现i的次数为：(更高位数字+1)x当前位数

 1 public class Solution {
 2     public int countDigitOne(int n) {
 3         //I will count how many 1s appear on each bit of n, respectively.
 4         if (n <= 0) return 0;
 5         long num = n;
 6         long bit = 1;
 7         int res = 0;
 8         while (num/bit > 0) {
 9             long upper = num/(bit*10);
10             long cur = num%(bit*10)/bit;
11             long lower = num%bit;
12             
13             if (cur < 1) 
14                 res += upper*bit;
15             else if (cur == 1) 
16                 res += upper*bit + lower + 1;
17             else
18                 res += (upper+1) * bit;
19                 
20             bit *= 10;
21         }
22         
23         return res;
24     }
25 }