# 4-line C++ O(N) solution using queue (detailed explanation)

• 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]`).

1. Initialize `q` with a single `2` representing the second `2` of `S`.
2. 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.
3. 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;
}
``````

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