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
