# Short Python using queue

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

• Good idea, using a list of ints instead of a string. Makes working with the digits easier. No need for the additional queue, though:

``````def magicalString(self, n):
S = [1, 2, 2]
i = 2
while len(S) < n:
S += S[i] * [3 - S[-1]]
i += 1
return S[:n].count(1)
``````

Or if we don't mind being a bit wasteful:

``````def magicalString(self, n):
S = [1, 2, 2]
for i in range(2, n):
S += S[i] * [3 - S[-1]]
return S[:n].count(1)``````

• @StefanPochmann You're right. Quite excited to read your comment actually. It is the 6th month since I decided to learn CS myself and I always learned a lot from your post. Hope someday I can be as good as you, :)

• @StefanPochmann I am learning CS ,too. But I have difficulty in solving the problem like this one. I fail to find the trick. How can I improve myself.

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