1053. The Largest Climbing Number Not Above n

Call a positive integer CLIMBING when its decimal digits never decrease from left to right, so 1234, 77, 9 and 1122388 all climb and 332 does not.

Given n, print the largest climbing number that is at most n.

332 -> 299 1234 -> 1234 already climbing 10 -> 9 dropping to one digit is allowed 551 -> 499

## What most people try first

Count down from n and test each number. On 10^18 the answer may be far below, and it is: 10^18 answers 999999999999999999, which is 10^18 - 1 steps away. This is the brute force this problem was checked against, for n up to 200000.

## Find the first fall, then give everything after it away

Write n as a digit string. If it already climbs, print it. Otherwise there is a position where a digit exceeds the next one.

The move is: lower that digit by 1, and set every digit after it to 9. Lowering makes the number smaller than n, so the tail is free, and 9s are the largest tail available.

The subtlety is that lowering a digit can create a NEW fall with the digit before it. 332 is exactly that: the fall is at index 1 (3 > 2), lowering gives 32 9 which reads 329, and now index 0 falls. So the scan has to run right to left and keep repairing.

d = digits of n mark = len(d) for i from len(d)-1 down to 1: if d[i-1] > d[i]: d[i-1] -= 1 mark = i for i from mark to len(d)-1: d[i] = 9 answer = the number d spells, with leading zeros dropped

On 332: i = 2 gives 3 > 2, so d becomes 3 2 2 with mark = 2; i = 1 gives 3 > 2, so d becomes 2 2 2 with mark = 1; filling from index 1 gives 2 9 9, which is 299.

## Why the answer is exactly this

Let p be the LEFTMOST position where the final answer differs from n. Since the answer is at most n and agrees with it before p, the digit at p must be strictly smaller. Once it is, every later digit is unconstrained, so the largest choice is all 9s, and the largest digit at p itself is d[p] - 1.

So the answer is determined by p alone, and it is a climbing number only if d[0] .. d[p-1] climbs and d[p] - 1 is at least d[p-1]. Among all workable p, the LARGEST wins, because a later p keeps more of n's high digits.

The right-to-left scan finds exactly that largest workable p: it starts at the first fall and drags left only when the borrow creates another one, which is precisely when the current p is not workable.

## Leading zeros, and the shorter answer

10 becomes 0 9, which must print as 9 rather than 09. Dropping leading zeros is part of the answer, not a formatting detail, because the true answer really does have fewer digits than n.

## The single-digit case

Any one-digit n climbs, so the loop never runs and the answer is n. A version that always lowers something answers 8 for 9.

## Overflow

n reaches 10^18, which needs a 64 bit integer: the signed 32 bit limit is 2147483647, and even 3 * 10^9 is past it. Working on the digit string avoids the problem entirely until the final conversion, which is why the reference solutions do that.

## Cost

Time O(number of digits), at most 19. Space O(1).

Constraints - `1 ≤ n ≤ 1000000000000000000`