PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: am_aadvik
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
(Optionally) Recursion
PROBLEM:
Given an integer N, find the smallest integer x \ge N that doesn’t contain D in its decimal representation.
EXPLANATION:
If N itself doesn’t contain D in its representation, the answer is simply N.
Otherwise, suppose the digits of N from left to right are d_1d_2\ldots d_k, and the leftmost occurrence of D is at digit i, i.e. d_i = D and d_j \ne D for j \lt i.
Then, when repeatedly incrementing the number starting from N, we’ll still have digit D present as long as d_i is unchanged.
The first time d_i will be changed, is when we reach the value
That is, everything till d_i remains the same, and then there’s a bunch of 9’s after it.
Then, adding 1 to this will increment d_i by 1, hence removing it.
However, this won’t always completely eliminate D, because:
- If D = 0 then we’ll create more zeros in the suffix of the number, since all the 9’s will become 0’s.
- If D = 9 then incrementing d_i will instead make it 0, and send a carry to earlier digits; so it’s possible an earlier 8 gets increased to 9.
While it’s possible to handle these cases separately (they both collapse into somewhat simple criteria), the easiest/fastest method to deal with everything, while also not needing casework, is to just use recursion.
Create the number d_1\ldots d_i999\ldots 999, then add 1 to it and recursively find the answer starting from this new number.
While doing this, each digit can be chosen as i (the leftmost occurrence of D) at most once; and so the overall recursive depth cannot exceed the number of digits - which is \mathcal{O}(\log N).
Since we do \mathcal{O}(\log N) work at each stage, the overall complexity is \mathcal{O}(\log^2 N) which is perfectly fast.
TIME COMPLEXITY:
\mathcal{O}(\log^2 N) per testcase.
CODE:
Editorialist's code (PyPy3)
def up(n, d):
if str(d) not in str(n): return n
i = str(n).index(str(d))
return up(int(str(n)[:i+1] + '9'*(len(str(n)) - i - 1)) + 1, d)
for _ in range(int(input())):
n, d = map(int, input().split())
print(up(n, d))