LeetCode Q233: Number of Digit One (hard*)

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.

// 我的解法的基本思想就是考虑把某一个位数上的数字设成1后，看其他位置有多少种选择。然后把每个数字位取1而有的选择都加起来就可以了。比如，假设输入为392， 那么把个位设置成1之后，十位和百位的选择就有00~39共40种，所以个位上可以有40个1。然后把十位设置成1之后，百位和个位有 00 ~39共40中选择，注意这儿并不是32或者33种，因为当10位上的数设成1之后，319也是小于392的，所以个位可以取所有的0~9。然后百位设成1后，十位和个位有00~99，共100种选择。

所以加起来就是： 40 + 40 + 100 = 180 种可能性，也就是180 个 1。

// A number is divided into three parts, front, curDigit and rear. For example, if input is 123456789, when we are considering the situation if we set the digit 5 to 1, then:

front = 1234, curDigit = 5, rear = 6789, rearSize = 1000

	class Solution {
	public:
	int countDigitOne(int n) {
	int rearSize = 1;
	long mod = 1;
	int count = 0;
	while(mod <= n){
	long front = n / (mod * 10);
	long rear = n % mod;
	int curDigit =(int) (n % (mod * 10)) / rearSize;
	if(curDigit > 1){
	count += ((front + 1) * rearSize);
	}
	else if(curDigit == 1){
	count += (front * rearSize + rear + 1);
	}
	else{
	count += (front * rearSize);
	}
	mod *= 10;
	rearSize *= 10;
	}
	return count;
	}
	};

view raw Q233.cpp hosted with ❤ by GitHub