RearrangeAndIncrement | Topcoder Archive

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 int[] with the following properties:

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.

Definition

Class:: RearrangeAndIncrement
Method:: change
Parameters:: int, int
Returns:: int[]
Method signature:: int[] change(int X, int Y)
(be sure your method is public)

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.

Examples

```
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.

Returns: {1111111, 1111122, 1111221, 1111232 }

Increment, rearrange, increment.

```
47
```
```
47
```
```
Returns: {47 }
```
A one-element sequence is a valid answer if X = Y.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.