<p>A magical string <code>s</code> consists of only <code>&#39;1&#39;</code> and <code>&#39;2&#39;</code> and obeys the following rules:</p>

<ul>
	<li>The string s is magical because concatenating the number of contiguous occurrences of characters <code>&#39;1&#39;</code> and <code>&#39;2&#39;</code> generates the string <code>s</code> itself.</li>
</ul>

<p>The first few elements of <code>s</code> is <code>s = &quot;1221121221221121122&hellip;&hellip;&quot;</code>. If we group the consecutive <code>1</code>&#39;s and <code>2</code>&#39;s in <code>s</code>, it will be <code>&quot;1 22 11 2 1 22 1 22 11 2 11 22 ......&quot;</code> and the occurrences of <code>1</code>&#39;s or <code>2</code>&#39;s in each group are <code>&quot;1 2 2 1 1 2 1 2 2 1 2 2 ......&quot;</code>. You can see that the occurrence sequence is <code>s</code> itself.</p>

<p>Given an integer <code>n</code>, return the number of <code>1</code>&#39;s in the first <code>n</code> number in the magical string <code>s</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 6
<strong>Output:</strong> 3
<strong>Explanation:</strong> The first 6 elements of magical string s is &quot;122112&quot; and it contains three 1&#39;s, so return 3.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
    int magicalString(int n) {
        if(n==0) return 0;
        vector<char> res;
        res.push_back('1');
        res.push_back('2');
        res.push_back('2');
        int i=2;
        while(res.size()<n){
            string temp="";
            int num= '3'-res[res.size()-1];
            // cout<<"i="<<i<<" num="<<num<<" res="<<res[i]<<endl;
            for(int j=0; j<res[i]-'0'; j++){
                // cout<<"j="<<j<<" "<<temp<<endl;
                temp+=to_string(num);
            }
            // cout<<temp<<endl;
            for(int m=0; m<temp.length(); m++){
                res.push_back(temp[m]);
            }
            i++;
        }
        // cout<<res<<endl;
        int count=0;
        for(int i=0; i<n; i++){
            if(res[i]-'0'==1) count++;
        }
        return count;
    }
};
11500