Problem Statement
Elly has invented a new way of encoding numbers. She has shown you the list 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211 and asked you what the next number is.
You've figured out that one quickly - the number is, obviously, 31131211131221. Well, probably not that obviously. What you've realized is that the girl splits each number into parts, consisting of consecutive equal digits and then writes the length of each such sequence and what digit it contains. For example 13112221 is split into 1, 3, 11, 222, 1 and then converted into "one time 1" (11), "one time 3" (13), "two times 1" (21), "three times 2" (32), and "one time 1" (11) = 1113213211.
You became rather smug that you figured it out. This annoyed Elly quite a bit and she thought of another challenge. Given a non-negative long N, find the smallest possible non-negative integer X, that would at some point lead to the given number using the above algorithm. For example, if she has given you 31131211131221, you should answer 1, and if the given number was 42, then your answer would be 42. (Note that 2222 would lead to 42, but 42 is smaller than 2222.)
To avoid ambiguity, Elly added a rule, that no number in the sequence should contain more than nine consecutive equal digits. That is, neither the number she gives you, nor the answer you are supposed to find, nor any number in the sequence between them can have more than nine consecutive equal digits.
You've figured out that one quickly - the number is, obviously, 31131211131221. Well, probably not that obviously. What you've realized is that the girl splits each number into parts, consisting of consecutive equal digits and then writes the length of each such sequence and what digit it contains. For example 13112221 is split into 1, 3, 11, 222, 1 and then converted into "one time 1" (11), "one time 3" (13), "two times 1" (21), "three times 2" (32), and "one time 1" (11) = 1113213211.
You became rather smug that you figured it out. This annoyed Elly quite a bit and she thought of another challenge. Given a non-negative long N, find the smallest possible non-negative integer X, that would at some point lead to the given number using the above algorithm. For example, if she has given you 31131211131221, you should answer 1, and if the given number was 42, then your answer would be 42. (Note that 2222 would lead to 42, but 42 is smaller than 2222.)
To avoid ambiguity, Elly added a rule, that no number in the sequence should contain more than nine consecutive equal digits. That is, neither the number she gives you, nor the answer you are supposed to find, nor any number in the sequence between them can have more than nine consecutive equal digits.
Definition
- Class:
- EllysEncoding
- Method:
- getMin
- Parameters:
- long
- Returns:
- long
- Method signature:
- long getMin(long N)
- (be sure your method is public)
Constraints
- N will be between 0 and 1018, inclusive.
Examples
31131211131221
Returns: 1
The example from the problem statement.13112221
Returns: 1
An earlier number from the same sequence.42
Returns: 42
Forty-two is preceded by 2222 (which, as it turns out, is the only other number that can lead to 42). However, since 42 is less than 2222, the answer is 42.31101211
Returns: 1011
Here the answer is 1011. Note that we consider only proper integers (without leading zeroes) - otherwise 01 would be even smaller number (and it generates 1011).4222
Returns: 4222
Note that if there was a number before 4222, it would consist of six 2s, which would be encoded as 62.1337
Returns: 1337
Note that if there was a number before 3777, it would contain 10 sevens, which would violate Elly's rule about "no more than 9 consecutive equal digits".13211431133112
Returns: 1432
Back to all problems