481. Magical String
Description
A magical string s
consists of only '1'
and '2'
and obeys the following rules:
- The string s is magical because concatenating the number of contiguous occurrences of characters
'1'
and'2'
generates the strings
itself.
The first few elements of s
is s = "1221121221221121122……"
. If we group the consecutive 1
's and 2
's in s
, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......"
and the occurrences of 1
's or 2
's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......"
. You can see that the occurrence sequence is s
itself.
Given an integer n
, return the number of 1
's in the first n
number in the magical string s
.
Example 1:
Input: n = 6 Output: 3 Explanation: The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 105
Solutions
Solution 1: Simulate the Construction Process
According to the problem, we know that each group of numbers in the string $s$ can be obtained from the digits of the string $s$ itself.
The first two groups of numbers in string $s$ are $1$ and $22$, which are obtained from the first and second digits of string $s$, respectively. Moreover, the first group of numbers contains only $1$, the second group contains only $2$, the third group contains only $1$, and so on.
Since the first two groups of numbers are known, we initialize string $s$ as $122$, and then start constructing from the third group. The third group of numbers is obtained from the third digit of string $s$ (index $i=2$), so at this point, we point the pointer $i$ to the third digit $2$ of string $s$.
1 2 2
^
i
The digit pointed by pointer $i$ is $2$, indicating that the third group of numbers will appear twice. Since the previous group of numbers is $2$, and the numbers alternate between groups, the third group of numbers is two $1$s, i.e., $11$. After construction, the pointer $i$ moves to the next position, pointing to the fourth digit $1$ of string $s$.
1 2 2 1 1
^
i
At this point, the digit pointed by pointer $i$ is $1$, indicating that the fourth group of numbers will appear once. Since the previous group of numbers is $1$, and the numbers alternate between groups, the fourth group of numbers is one $2$, i.e., $2$. After construction, the pointer $i$ moves to the next position, pointing to the fifth digit $1$ of string $s$.
1 2 2 1 1 2
^
i
Following this rule, we simulate the construction process sequentially until the length of string $s$ is greater than or equal to $n$.
The time complexity is $O(n)$, and the space complexity is $O(n)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|