Magical String

The problem asks us to return the number of ‘1’s in the first n numbers in the magical string s. The magical string is defined recursively, where the occurrences of ‘1’s and ‘2’s define the next characters in the string.

Here’s a step-by-step guide to solve the problem:

Initialize the magical string: Start with the first characters as “122” since it forms the base of the string.
Generate the string: Use a pointer to iterate through the string, where the value at the current pointer determines the number of times to repeat the next character (1 or 2) in the sequence.
Count the ‘1’s: As you generate the string, keep track of the number of ‘1’s in the string.
Stop when needed: Once the length of the string reaches n, stop the generation and return the count of ‘1’s.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def magicalString(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 3:
            return 1

        s = [1, 2, 2]
        pointer = 2 # Pointer to iterate through s

        # Generate the magical string up to n
        while len(s) < n:
            # Append the next character based on the current pointer
            # Alternate between 1 and 2
            s += [3 - s[-1]] * s[pointer]
            pointer += 1

        return s[:n].count(1)

Explanation for the example n = 6:

Start with s = “122”
First iteration: Read 2 from the pointer, so append two 1’s -> s = “12211”
Second iteration: Read 2 from the pointer, so append two 2’s -> s = “122112”

The first 6 characters of the magical string contain three ‘1’s, so the code returns 3.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def magicalString(self, n: int) -> int:
        if n <= 0:
            return 0
        if n <= 3:
            return 1

        a = [0] * (n + 1)
        a[0], a[1], a[2] = 1, 2, 2
        head, tail, num, result = 2, 3, 1, 1

        while tail < n:
            for i in range(a[head]):
                a[tail] = num
                if num == 1 and tail < n:
                    result += 1
                tail += 1
            # XOR operation to toggle num between 1 and 2
            num ^= 3
            head += 1

        return result