LintCode "Digit Counts" !!

时间:2021-07-09 22:53:02

Lesson learnt: one effective solution for bit\digit counting problems: counting by digit\bit

http://www.hawstein.com/posts/20.4.html

class Solution {
public:
/*
* param k : As description.
* param n : As description.
* return: How many k's between 0 and n.
*/
int digitCounts(int k, int n) {
int ret = ;
int base = ;
while (n/base > )
{
int cur = (n/base) % ;
int low = n - (n/base) *base;
int high= n / (base * ); ret += high * base; // at least this many
if (cur == k)
{
ret += low + ; // all k-xxxxx
}
else if(cur > k)
{
if(!(!k && base > )) // in case of 0
ret += base; // one more base
}
base *= ;
}
return ret;
}
};