1396. The Smallest Base That Makes It a Palindrome

Print the smallest base b with b ≥ 2 in which n is written as a palindrome.

n = 3 -> 2 3 in base 2 is 11 n = 10 -> 3 10 in base 3 is 101 n = 2 -> 3 2 in base 2 is 10, not a palindrome; in base 3 it is 2 n = 1 -> 2 1 in base 2 is 1

An answer always exists: in any base above n the value is a single digit, and a single digit is a palindrome. So b = n + 1 always works, and the question is only how much smaller the smallest base is.

## What most people try first

Try every base from 2 upward, converting and checking. That is O(n) bases, each costing a conversion, so about 2 * 10^7 digit operations at the top of the range for a single query, and there can be 1000 queries.

## Two regimes, split at the square root

How many digits n has in base b depends on where b sits relative to n:

b*b <= n -> three or more digits sqrt(n) < b <= n -> exactly two digits b > n -> exactly one digit

The first regime has only sqrt(n) bases in it, which is 1000 at n = 10^6, so those can simply be checked one by one. The other two regimes contain almost all the bases, and they are settled by algebra instead of by search.

## The two-digit regime, solved by divisors

With exactly two digits, n = hi * b + lo where hi = n / b and lo = n mod b and 1 ≤ hi < b and 0 ≤ lo < b. A two-digit palindrome means hi = lo, say both equal r. Then:

n = r * b + r = r * (b + 1)

So r must divide n, and b = n / r - 1. That turns a search over up to 10^6 bases into a walk over the divisors of n, of which there are at most 240 below 10^6. Each candidate b is kept only if b ≥ 2, if r < b so the digits are legal, and if b*b > n so the value really has two digits and the first regime has not already been searched.

## The one-digit regime

b > n gives a single digit, always a palindrome, and the smallest such base is n + 1. That is the fallback, and it is the answer exactly when nothing smaller works, as for n = 2.

## Why the smallest is found

The three regimes partition every base at least 2, so taking the minimum over all candidates from all three is the true minimum. Within the first regime the loop runs upward and stops at its first hit, which is the smallest base with three or more digits. The second and third regimes contribute candidates that are all larger than sqrt(n), so a hit in the first regime always wins and the others need not even be computed.

## Overflow

Nothing here can overflow. n is at most 10^6, and the only products formed are b * b and r * r, which both stop at 10^6. A signed 32-bit integer reaches 2147483647, so there is three orders of magnitude of headroom. This is stated because most problems in this block do overflow, and the cap on n here is what keeps the brute-force check that verified these outputs affordable.

## Cost

O(sqrt(n) log n) per query.

Constraints - `1 ≤ q ≤ 1000` - `1 ≤ n ≤ 1000000` - A single digit counts as a palindrome, so `b = n + 1` always works.