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 stepbystep 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:


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
.

