You get inside and take the elevator to its only other stop: the gift shop. “Thank you for visiting the North Pole!” gleefully exclaims a nearby sign. You aren’t sure who is even allowed to visit the North Pole, but you know you can access the lobby through here, and from there you can access the rest of the North Pole base.
Full source can be found: in GitHub
Problem statement
You are given ranges of product IDs like: 998-1012 1188511880-1188511890
An ID is invalid if its digits consist of a smaller sequence repeated:
- Part 1: exactly twice (e.g.
55,6464,123123) - Part 2: two or more times (e.g.
111111,121212,123123123)
The task is to find all such IDs inside the ranges and compute their sum.
Processing the input
Ranges are parsed once and stored as (lower, upper) pairs.
1private record Range(long lower, long upper) {}
2
3public void readInput() {
4 for (String range : inputLoader.split(",")) {
5 String[] bounds = range.trim().split("-");
6 ranges.add(new Range(Long.parseLong(bounds[0]), Long.parseLong(bounds[1])));
7 }
8}
Part 1 solution
A number made of k digits repeated twice looks like:
x followed by x => x * (10^k + 1)
Example:
64→6464 = 64 × 101123→123123 = 123 × 1001
Instead of iterating over all IDs, we iterate over:
- digit length
k - possible base values
x - and compute valid ranges mathematically
The algorithm
For this algorithm to work the I added the following support methods to the Algo class:
1public static long floorDivPositive(long a, long b) {
2 // assumes a >= 0 and b > 0
3 return a / b;
4}
5
6public static long ceilDivPositive(long a, long b) {
7 // assumes a >= 0 and b > 0
8 return (a + b - 1L) / b;
9}
And then used them in the main algorithm:
1private long sumInvalidIdsInRange(long lower, long upper) {
2 BigInteger sum = BigInteger.ZERO;
3
4 for (int k = 1; k <= 9; k++) {
5 long pow10k = (long) Math.pow(10, k);
6 long multiplier = pow10k + 1;
7
8 long xMinDigits = pow10k / 10;
9 long xMaxDigits = pow10k - 1;
10
11 long xFrom = Math.max(
12 xMinDigits,
13 ceilDivPositive(lower, multiplier)
14 );
15 long xTo = Math.min(
16 xMaxDigits,
17 floorDivPositive(upper, multiplier)
18 );
19
20 if (xFrom > xTo) continue;
21
22 BigInteger count = BigInteger.valueOf(xTo - xFrom + 1);
23 BigInteger sumX = BigInteger.valueOf(xFrom)
24 .add(BigInteger.valueOf(xTo))
25 .multiply(count)
26 .divide(BigInteger.TWO);
27
28 sum = sum.add(BigInteger.valueOf(multiplier).multiply(sumX));
29 }
30 return sum.longValue();
31}
Concepts Used
- Digit length enumeration
- Closed-form arithmetic series
$$\sum_{x=a}^{b} x = \frac{(a+b)(b-a+1)}{2}$$ - Ceiling / floor division to restrict values to the range
- BigInteger to avoid overflow
This allows summing millions of candidate IDs in constant time per digit length.
Part 2 solution
Now an invalid ID:
- Has any repeating block length
- Repeats at least twice
- Covers the full number length
Examples:
111111→1repeated 6 times121212→12repeated 3 times123123123→123repeated 3 times
Main algorithm
- Group numbers by total digit length
n - For each
n, find all period lengthspwherep | n - Compute numbers of the form:
x repeated (n / p) times
- Use inclusion–exclusion to ensure each number is counted once, by its minimal period.
Translated into code that would be:
1private static BigInteger sumInvalidInRange(long lower, long upper) {
2 BigInteger total = BigInteger.ZERO;
3
4 int minLen = digits(lower);
5 int maxLen = digits(upper);
6
7 for (int n = minLen; n <= maxLen; n++) {
8 long lo = Math.max(lower, (long) Math.pow(10, n - 1));
9 long hi = Math.min(upper, (long) Math.pow(10, n) - 1);
10 if (lo <= hi) {
11 total = total.add(sumInvalidFixedLength(n, lo, hi));
12 }
13 }
14
15 return total;
16}
17
18// Handle the fixed lenght numbers
19private static BigInteger sumInvalidFixedLength(int n, long lo, long hi) {
20 List<Integer> ps = divisors(n); // sorted
21 BigInteger[] periodSum = new BigInteger[n + 1];
22 BigInteger[] minSum = new BigInteger[n + 1];
23 for (int i = 0; i <= n; i++) {
24 periodSum[i] = BigInteger.ZERO;
25 minSum[i] = BigInteger.ZERO;
26 }
27
28 // Compute sums for "has period p" (not minimal yet)
29 for (int p : ps) {
30 if (p == n) continue;
31 periodSum[p] = sumWithPeriod(n, p, lo, hi);
32 }
33
34 // Turn that into "has minimal period p" by subtracting smaller divisor contributions
35 for (int p : ps) {
36 if (p == n) continue;
37
38 BigInteger s = periodSum[p];
39 for (int d : ps) {
40 if (d >= p) break;
41 if (p % d == 0) {
42 s = s.subtract(minSum[d]);
43 }
44 }
45 minSum[p] = s;
46 }
47
48 BigInteger total = BigInteger.ZERO;
49 for (int p : ps) {
50 if (p == n) continue;
51 total = total.add(minSum[p]);
52 }
53 return total;
54}
55
56private static BigInteger sumWithPeriod(int n, int p, long lo, long hi) {
57 int repeats = n / p;
58 long m = repeatMultiplier(p, repeats);
59
60 long xMin = (long) Math.pow(10, p - 1);
61 long xMax = (long) Math.pow(10, p) - 1;
62
63 long from = Math.max(xMin, ceilDiv(lo, m));
64 long to = Math.min(xMax, floorDiv(hi, m));
65 if (from > to) return BigInteger.ZERO;
66
67 BigInteger count = BigInteger.valueOf(to - from + 1L);
68 BigInteger a = BigInteger.valueOf(from);
69 BigInteger b = BigInteger.valueOf(to);
70
71 BigInteger sumX = a.add(b).multiply(count).divide(BigInteger.TWO);
72 return BigInteger.valueOf(m).multiply(sumX);
73}
1private static long repeatMultiplier(int p, int repeats) {
2 // m = 1 + 10^p + 10^(2p) + ... + 10^((repeats-1)p)
3 long tenPowP = (long) Math.pow(10, p);
4 long m = 1L;
5 long term = 1L;
6 for (int i = 1; i < repeats; i++) {
7 term *= tenPowP;
8 m += term;
9 }
10 return m;
11}
The final part of the code is to actually loop over all of the ranges and compute the number:
1ranges.stream()
2 .map(r -> sumInvalidInRange(r.lower, r.upper))
3 .reduce(BigInteger::add)
4 .orElseThrow()
5 .longValue();