3
\$\begingroup\$

Problem Statement

Every book has n pages with 1 to n pages. The summary is made by adding up the number of digits of all page numbers.

Task: Given the summary, find the number of pages n the book has.

Example

If the input is summary=25, then the output must be n=17: The numbers 1 to 17 have 25 digits in total: 1234567891011121314151617.

Be aware that you'll get enormous books having up to 100.000 pages.

My Solution

In my approach to this problem, I have tried multiple inputs and saw a pattern.

The first 9 numbers have 1 digit, the next 90 numbers until 99 have 2 digits, numbers starting from 100 to 999 has 3 digits the total of 900 it goes on like this.

I see a pattern.

9 + 9 * Math.pow(10,1) * 2 + 9 * Math.pow(10,2) * 3 + ...+ 9 * 10 * Math.pow(10,n-1) * n

In case of summary = 1095:

9 + 9 * 10 * 2 + 3X = 1095 (9 * 100 * 3 exceeds the total, so I stop the series and see how many of 3 digit numbers contributed to the summary)

189 + 3X = 1095

X = (1095 -189) /3

X = 302

So total series goes like this 9 + 90 + 302 = 401

The answer is 401.

    private static int amountOfPages(int summary) {
        int N = summary, totalNumbersSoFar = 0, pagesSoFar = 0;
        StringBuilder nineSeries = new StringBuilder("9");
        while (Integer.parseInt(nineSeries.toString()) < (N / nineSeries.length())) {
            int numbersInRange = (int) (Math.pow(10, nineSeries.length() - 1) * 9);
            pagesSoFar += numbersInRange * (nineSeries.length());
            N -= numbersInRange;
            totalNumbersSoFar += numbersInRange;
            nineSeries.append("9");
        }
        return ((summary - pagesSoFar) / nineSeries.length()) + totalNumbersSoFar;
    }

My solution has passed test cases and is within the allowed time and memory limit, but I'm not so content with the implementation.

\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

To analyse this operation it's first important to understand its inverse.

Calculating the "summary" sum from the page count is possible in O(1) analytically with no loops due to the geometric series property:

$$ ...4321 = \sum _{i=0} ^{n-1} (i+1) 10^i = \frac {n 10^n} {10 - 1} - \frac {10^n - 1} {(10 - 1)^2} $$

which means that the summary can be calculated as

private static int getSummary(int npages) {
    int D = (int)Math.log10(npages),
        n10 = (int)Math.pow(10, D);

    return (1 - n10)/9 + D*n10 + (D+1)*(npages - n10 + 1);
}

An iterative solution to this function's inverse is probably necessary, because - to do it analytically - it would require the analytic continuation of the product log function. An analytic solution may be possible by calling into a Lambert W implementation if you have access to a numerical library, though it's dubious whether that would perform better than a simple iterative solution.

Still, we can do better than your implementation. You use strings (in fact an entire StringBuilder!) when you should not. Also, don't call Math.pow. Instead, iterate as if you were calculating a summary total until the iterative summary exceeds the actual summary. Then, once you know the number of digits of the page count, you can subtract the remainder, divide by the known number of digits, and get the actual page count. Note that for the problem's stated maximum page count of 100,000, the corresponding summary value is only about 500,000, so there is no risk of overflow.

    private static int getPagesNew(int summary) {
        int whole = 0, newWhole = 0, pages = 0, d = 1;
        for (int fac = 9; newWhole < summary; fac *= 10, d++) {
            whole = newWhole;
            pages += fac/10;
            newWhole += fac * d;
        }
        return pages + (summary - whole)/(d - 1);
    }

For your test quantity of pages=401 summary=1095, this is equivalent. However, there are some cases of yours that seem to not make a lot of sense:

public class App {
    private static int getSummaryBrute(int npages) {
        int summary = 0;
        for (int p = 1; p <= npages; p++)
            summary += Integer.toString(p).length();
        return summary;
    }

    private static int getSummary(int npages) {
        int D = (int)Math.log10(npages),
            n10 = (int)Math.pow(10, D);

        return (1 - n10)/9 + D*n10 + (D+1)*(npages - n10 + 1);
    }

    private static int getPagesOriginal(int summary) {
        int N = summary, totalNumbersSoFar = 0, pagesSoFar = 0;
        StringBuilder nineSeries = new StringBuilder("9");
        while (Integer.parseInt(nineSeries.toString()) < (N / nineSeries.length())) {
            int numbersInRange = (int) (Math.pow(10, nineSeries.length() - 1) * 9);
            pagesSoFar += numbersInRange * (nineSeries.length());
            N -= numbersInRange;
            totalNumbersSoFar += numbersInRange;
            nineSeries.append("9");
        }
        return ((summary - pagesSoFar) / nineSeries.length()) + totalNumbersSoFar;
    }

    private static int getPagesNew(int summary) {
        int whole = 0, newWhole = 0, pages = 0, d = 1;
        for (int fac = 9; newWhole < summary; fac *= 10, d++) {
            whole = newWhole;
            pages += fac/10;
            newWhole += fac * d;
        }
        return pages + (summary - whole)/(d - 1);
    }

    private static void test(int npages) {
        int summary = getSummary(npages);
        assert summary == getSummaryBrute(npages);
        assert npages == getPagesNew(summary);
        int actual = getPagesOriginal(summary);
        if (actual != npages) {
            System.out.printf(
                "Old method failed for summary=%d: expected pages=%d, actual=%d%n",
                summary, npages, actual
            );
        }
    }

    public static void main(String[] args) {
        assert 1095 == getSummaryBrute(401);
        assert 1095 == getSummary(401);
        assert 401 == getPagesOriginal(1_095);
        assert 401 == getPagesNew(1_095);

        for (int npages = 1; npages <= 1_001; npages++)
            test(npages);

        for (int fac = 1; fac <= 10_000_000; fac *= 10) {
            if (fac > 1) test(fac - 1);
            test(fac);
            test(fac + 1);
            test(5 * fac);
        }
    }
}

outputs

Old method failed for summary=195: expected pages=101, actual=102
Old method failed for summary=198: expected pages=102, actual=103
Old method failed for summary=201: expected pages=103, actual=105
Old method failed for summary=204: expected pages=104, actual=106
Old method failed for summary=207: expected pages=105, actual=108
Old method failed for summary=195: expected pages=101, actual=102
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.