A Google's Interview Question - GLAT #20 series 4

The entire class is as follows:

java 代码

/**
* GOOGLE GLAT question #20:
* 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?
*/
public class CountOnesUseIteration
{
    // Implementation notes:
    // There are various places we can optimize the code, however I don't
    // feel we need to do so since the implementation is fast enough.

    private static final int ITERATION_LIMIT = 10000;

    // This is used to check whether any given func value is between the
    // function values of 10^n and 2*10^n so that we know the corresponding
    // number starts with 1 or not, this fact will determine which formula
    // to use for reverse iteration.
    long[] x1 = new long[9];
    long[] x2 = new long[9];
    long[] y1 = new long[9];
    long[] y2 = new long[9];

    public CountOnesUseIteration()
    {
        for (int i=1; i<10; i++)
        {
            x1[i-1] = power(10, i);
            x2[i-1] = 2 * x1[i-1] - 1;
            y1[i-1] = numOfOnes(x1[i-1]);
            y2[i-1] = numOfOnes(x2[i-1]);
        }
    }

    public void countDigitOne()
    {
        long begin = System.currentTimeMillis();

        long loop = 10000000000L;

        int iterationTimes = 1;
        while (loop > 0 && iterationTimes < ITERATION_LIMIT)
        {
            long func = numOfOnes(loop);
            if (func == loop)
            {
                System.out.println("-----> found a fixed point: x=" + loop);
                // now skip this one and keep going for the next one.
                loop--;
            }
            else
            {
                if (func < loop) // we force this to go to the left.
                {
                    loop = func;
                }
                else // func > loop
                {
                    func = inverseFunc(loop);
                    if (func < loop && numOfOnes(func) >= loop)
                    {
                        loop = func;
                    }
                    else
                    {
                        loop --; // if we can't find one, just decrement it.
                    }
                }
            }

            iterationTimes++;
        }

        System.out.println("It takes " + (System.currentTimeMillis() - begin) + " milli");
        System.out.println("It takes " + iterationTimes + " iterations");
    }

    // function value
    private long numOfOnes(long x)
    {
        // recursion stops
        if (x <= 0) return 0;
        if (x == 1) return 1;

        int powerk = 0;
        long tenPowers = 1;
        long leadingDigit = x;
        while (leadingDigit >= 10)
        {
            leadingDigit /= 10;
            powerk++;
            tenPowers *= 10;
        }

        long reminder = x - leadingDigit * tenPowers;
        if (leadingDigit == 1)
        {
            return powerk * tenPowers / 10 + 1 + reminder + numOfOnes(reminder);
        }
        else
        {
            return leadingDigit * powerk * tenPowers / 10 + tenPowers + numOfOnes(reminder);
        }
    }

    // kind of inverse function value
    public long inverseFunc(long y)
    {
        // we are moving backward to find a x such that x < y <= f(x) and keep x as small as possible.

        // recursion default.
        if (y <= 0) return 0;
        if (y == 1) return 1;
        if (y == 2) return 10;

        // check whether y is in 1's range
        int m = isInOneRange(y);
        if (m != -1)
        {
            long tmp = y - (m + 1) * power(10, m) - 1;
            long inc = findRoot(tmp);
            return power(10, m + 1) + inc;
        }
        else
        {
            int k = numOfDigits(y) - 1;
            long tmp = y - power(10, k);
            long ak = tmp / (k * power(10, k - 1));
            if (ak > 9) ak = 9; // leave the rest to the recursion
            long remainder = tmp - ak * k * power(10, k - 1);
            long xRemainder = inverseFunc(remainder);
            return ak * power(10, k) + xRemainder;
        }
    }

    private int isInOneRange(long y)
    {
        // This is to check whether the func value is between the function values of 10^n and 2*10^n.

        // this can be done faster since it's sorted, but again I am lazy
        int k=-1;
        for (int i=0; i<9; i++)
        {
            if (y <= y2[i])
            {
                k = i;
                break; // first smaller, break out
            }
        }

        if (k==-1) return -1;

        if (y >= y1[k]) return k;
        else return -1;
    }

    private static int numOfDigits(long x)
    {
        int i = 0;
        while (x > 0)
        {
            x /= 10;
            i++;
        }

        return i;
    }

    private static long power(long base, int power)
    {
        long ret = 1;
        for (int i=1; i<=power; i++) ret *= base;
        return ret;
    }

    public long findRoot(long y)
    {
        // find a root for  x + f(x) = y, where f is the number of one's function in the above.
        // we need a x such that x + f(x)>=y, the least x.
        // Note that x + f(x) is a mononically increasing function.
        long x0 = 0;
        long x1 = y;
        long x;
        while (x1 - x0 > 1)
        {
            x = x0 + (x1 - x0) / 2;
            long func = numOfOnes(x) + x;
            if (func == y) return x;
            if (func < y)
            {
                x0 = x;
            }
            else
            {
                x1 = x;
            }
        }

        if (x0 + numOfOnes(x0) == y) return x0;
        else return x1;
    }
}

There are possible places where we can speed up further, but hardly worth it.