**Algorithm:**

Starting from prefix `"122"`

of magical string `S`

, we use a `queue<int> q`

to store its digits from the second `2`

(i.e., `S[2]`

).

- Initialize
`q`

with a single`2`

representing the second`2`

of`S`

. - Scan and pop the front of
`q`

and push`q.front()`

many of`d`

's into`q`

, where both`q.front()`

and`d`

are`2`

and`1`

and they alternate each time when scanned. - Repeat Step 2 until the max desired length
`L == n`

of the magical string is scanned. Meanwhile, also update digit 1's count`ones`

whenever`d == 1`

.

**Note:**

`d ^= 3`

flips`d`

between`1`

and`2`

. You can also use`d = 3-d`

as well.- The outer loop has size
`n-3`

and inner loop has max size`2`

, so`O(n)`

for time complexity.

```
int magicalString(int n) {
int ones = 1; queue<int> q({2});
for (int L = 3, d = 1; L < n; d ^= 3, q.pop())
for (int i = 0; i++ < q.front() && L++ < n; q.push(d), ones += d%2) ;
return n? ones : 0;
}
```