fentoyal
BAN USERI will just post a working code. You can test it out yourself. Pure C++.
The complexity,
countOccur -- O(logN) , N < 19*K
lowerBound -- O(log(19*K))
total: O(logN*log19K) = O ((log19K)^2)
#include <iostream>
#include <vector>
using namespace std;
//Count occurrence of digit d within number 1~n.
//It assumes n > 0 and d in [0,9]
int countOccur(int n, int d)
{
int sum = 0, l = 1, r = 0;
for (; n >= 1; n /= 10)
{
int q = n/10;
int m = n%10;
if (m > d)
{
q ++;
}
if (m == d)
{
sum += r + 1;
}
if (d == 0)
{
q --;
}
sum += q*l;
r = m*l + r;
l *= 10;
}
return sum;
}
//Find the lower bound of n, given digit d
//and occurrence k.
int lowerBound(int d, int k)
{
int l = 1, h = k*19;
while (l < h - 1)
{
int m = (l + h) / 2;
int c = countOccur(m, d);
if ( c < k)
{
l = m;
}else if (c >= k){
h = m;
}
}
return h;
}
int solve(int d, int k)
{
cout<<"["<<lowerBound(d, k)<<", "<<lowerBound(d, k+1)<<")"<<endl;
return 1;
}
int main()
{
cout<<countOccur(11,0)<<endl;
solve(0,5);
}
I will just post a working code. You can test it out yourself. Pure C++.
The complexity,
countOccur -- O(logN) , N < 19*K
lowerBound -- O(log(19*K))
total: O(logN*log19K) = O ((log19K)^2)
- fentoyal February 06, 2015