Is the magical string unique?


  • 15
    X

    Based on the rule, if start with 2, I can get string:
    2211212212211....

    Compare with the one in the problem 12211212212211...., it removes the prefix 1.

    If that is correct, for some N like 5, then the answer will be different depending on which one we are referring to.


  • 0
    H
    This post is deleted!

  • 1
    R

    @xiaoboluo Yes, I agree with you.


  • 0
    J

    I agree, this question is bit ambiguous. Leetcode should clarify it.


  • 0
    A
    This post is deleted!

  • 0
    D

    @xiaoboluo You're right. The string is not unique, and it can have as many cases as you want. Like: 333111222121221122...
    4444111122223333...
    5555511111......
    ......
    LOL


  • 1
    D

    @xiaoboluo, @rgc588, @jahuja, @davidchai
    No, it's unique! And since the starting sequence of the magic number is given, we don't have to assume, that "what if number starts with 2". It just starts with 1 and that's it.

    I didn't understand the problem completely at the beginning, thinking that any sequence is good, but it's not.

    Here is a photo from my notes, so you can see how I've seen it during solving the problem.
    0_1508145893098_IMG_1444.jpg

    Here is the idea. 2 rows. one for numbers/digits in sequence and the seconds one for occurrence.

    We start with 1, meaning we have 1 occurrence of 1.
    1
    1

    Then we insert 2 in our sequence. For the condition to work: "concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself."

    It implies that we need to have 22 in our sequence, since only then the number of contiguous occurrence of character '2' will generate the string S itself. If the number of occurrence will be 1, then we will have:
    1 2
    1 1
    which is obviously not the same.

    Then we see that for this to be true, the next occurrence should be also 2 (the second number from number 22) so that it will match:
    1 22 x
    1 2 2

    Obviously instead of x we insert 11, the digit is 1, because we switch from 1 to 2 and from 2 to 1, and 11 and not 1, because the number of occurrence is 2 and not 1.

    I guess you got the logic. Using this "algorithm" the generated number is unique.


    PS. I've figured out that it's a Kolakoski sequence, take a look: https://en.wikipedia.org/wiki/Kolakoski_sequence
    Maybe Wiki explanation is better :P


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.