Interview Questions And Answers 
-
Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?
1,739 Views |
(9 votes, avg: 4.33)
Loading ...
Answers »
Our Sponsors
Our Sponsors
This is a naive, but correct solution:
First, a function that counts all the ‘1’s that appear in a given integer:
int countOnes(int n)
{
int count = 0;
while (n _GREATERTHAN_ 0)
{
int m = (n / 10) * 10;
int rest = n - m;
count += (rest == 1);
n = m / 10;
}
return count;
}
And now, the following function does what we’re asked:
int countOnesUntil(int n)
{
int count = 0;
for (int i = 0; i _LESSOREQUALTHAN_ n; i++)
{
count += countOnes(i);
}
return count;
}
Regarding the last question. It shouldn’t be hard to mathematically prove that there’s no number x > 1 such that countOnesUntil(x) == x.
Anyway you can execute this…
for (int x = 0; x _LESSTHAN_ 100000; x++)
{
int ones = countOnesUntil(x);
if (x == ones)
printf(”found!!! - %d\n”, x);
}
By a calculation it can be seen that,
f(100) = 21
f(1000) = 301
f(10000) = 4001
f(100000) = 50001
f(1000000) = 600001
In other words, the value of f increases by a fixed
series between integer multiples of 100. If d(n) is
the difference between f(pow(10,n)) - f(pow(10,n-1)),
then
d(3) = 280
d(4) = 3700
d(5) = 46000
d(6) = 550000
Similarly,
d(7) = 6400000
d(8) = 73000000
d(9) = 820000000
d(10) = 9100000000
f(pow(10, 10)) = f(pow(10,6)) + d(7) + d(8) + d(9) + d(10)
= 10000000001
So f(pow(10, 10) + 1) = 10000000001
In other words f(10000000001) = 10000000001
Or n is equal to 10000000001.
Well the answer is slightly wrong (1 off),
f(10000000000) = 10000000001
So f(10000000001) = 10000000002
And f(10000000002) = 10000000002
So answer is 10000000002.
Leave an Answer/Comment