Since how many current "1" or "2" depends on previous number in S, we can use a queue to get the corresponding information we need. Every time we update S, we update queue as well.

Updated: based @StefanPochmann 's idea, we can only use an index to indict current number of value we need.

```
class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
S = [1,2,2]
idx = 2
while len(S) < n:
S += S[idx] * [(3 - S[-1])]
idx += 1
return S[:n].count(1)
```

Old version:

```
class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
queue = collections.deque([2])
S = [1,2,2]
while len(S) < n:
k = queue.popleft()
tmp = 3 - S[-1]
for i in range(k):
S.append(tmp)
queue.append(tmp)
return S[:n].count(1)
```