quoc.honza
BAN USERRuns in constant time. Uses recursion and written in C++
int countExclude4(int n) {
return (n - countContain4(n-1));
}
int countContain4(int n) {
int factor = -1;
int k = n;
// Reached the unit digit
if (k < 4) return 0;
else if (k < 10) return 1;
// Find the highest factor of n
while (k > 0) {
factor++;
k /= 10;
}
// Find the number of numbers containing 4 in n/10
int prevMax = 0;
for (int i = 0; i < factor; ++i)
prevMax = (prevMax * 9) + (int)pow(10, i);
int quotient = n / (int)pow(10,factor);
int remainder = n % (int)pow(10,factor);
int sum = 0;
// e.g 4 in 45623
if (quotient == 4)
sum = quotient * prevMax + (remainder + 1);
// e.g 1 in 10000
else if (quotient == 1 && remainder == 0)
sum = prevMax;
// e.g 2 in 273
else if (quotient < 4)
sum = quotient * prevMax + countContain4(remainder);
// e.g 7 in 720324
else
sum = (quotient-1) * prevMax + (int)pow(10, factor) + countContain4(remainder);
return sum;
}
not sure if this is correct. I compared it to the brute force method and my own method and they do not agree.
- quoc.honza January 30, 2014