RearrangeAndIncrement
2022 TCO Parallel 2A · 2022-04-14 · by misof
Problem Statement
You have two ways of modifying a positive integer: you can either rearrange its digits, or you can make a small increment.
- When rearranging digits, the new number must have exactly the same digits as the old number, but they can appear in any order. (If the old number contains some zeros, they can become leading zeros when rearranging the digits. However, note that adding extra zeros is not allowed.)
- When incrementing the number, you can add any integer between 1 and 13, inclusive.
For example:
- You can rearrange 10234 to 01234 or to 42013, but not to 10203040. If you rearrange 10234 to 01234, your new number has the value 1234: the leading zero is discarded after the operation.
- You can increment 10234 to 10235 or 10247, but not to 10248.
Given the positive integers X and Y, transform X to Y in reasonably few steps.
Return a
- The number of elements is at most 200.
- The first element is X and the last element is Y.
- Each element is between 1 and 2,000,000,000, inclusive.
- Each element after the first can be obtained from the previous one by performing one legal transformation.
Notes
- For the given constraints a solution always exists.
- Any valid solution will be accepted. It is not necessary to minimize its length.
Constraints
- X will be between 1 and 999,999,999, inclusive.
- Y will be between 1 and 999,999,999, inclusive.
10234
1247
Returns: {10234, 1234, 1247 }
We first rearrange 10234 to 01234, and then we take the number 1234 we just produced and increment it by 13.
10234
10248
Returns: {10234, 10244, 10248 }
As the difference is 14, we cannot do it in a single increment, but we can surely do it in two.
999997
1000001
Returns: {999997, 999998, 999999, 1000000, 1000001 }
Just for fun we increment the current number by 1 four times. Note that the number of digits changes in one of the steps.
1000000
1000
Returns: {1000000, 1000 }
We can rearrange 1000000 to 0001000, which is the same as 1000.
1111111
1111232
Returns: {1111111, 1111122, 1111221, 1111232 }
Increment, rearrange, increment.
47
47
Returns: {47 }
A one-element sequence is a valid answer if X = Y.
Submissions are judged against all 246 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RearrangeAndIncrement with a public method vector<int> change(int X, int Y) · 246 test cases · 2 s / 256 MB per case