# C++ using queue (3ms)

• ``````int magicalString(int n) {
if (n==0)
return 0;
if (n<4)
return 1;

// Let's initialize
// digit stream : 1 22
// counts       : 1 2
// We'll keep the 'unused' part of the digit stream in a queue
// in this case, since the first 2 digits are used in the 'counts' stream,
// we initialize the queue with 2, the third digit
queue<int> s;
s.push(2);
// cnt is the number of digits in the stream so far
int cnt = 3;
// res is the number of ones so far
int res = 1;

// last digit used
int lastOne = 2;
while (cnt<n){
// m is the number of time swe used repeat the next digit
int m = s.front();
s.pop();

// swith from 1 to 2 or 2 to 1
if (lastOne == 2)
lastOne = 1;
else
lastOne = 2;

// if we are going to add 1 digit
if (m == 1){
s.push(lastOne); // add to the queue
cnt++;
if (lastOne==1)
res++;
}else{
// if we are going to add 2 digits
s.push(lastOne); // add to the queue
s.push(lastOne); // twice
cnt = cnt + 2;
if (lastOne==1)
res = res+2;
}
}
// if we pass n by 1, if we added 2 after n-1...
if (cnt == n+1 && lastOne == 1)
res--;

return res;
}``````

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