Magical string**S** only contains '1' and '2' and adheres to the following rules:

String**S** is magical because the consecutive occurrences of the concatenation characters '1' and '2' generate a string**S** itself.

String**The first few elements of S** are as follows:**S **= “1221121221221121122 ......”

If we will**Grouping consecutive 1 and 2 in S** will become:

1 22 11 2 1 22 1 22 11 2 11 22 ......

And the number of occurrences of '1' or '2' in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ......

You can see that the number of occurrences above is**S** itself.

Given an integer N as input, return a magic string**The number of '1's in the first N numbers in S||.**中前 N 个数字中的 '1' 的数目。

**Note: **N does not exceed 100,000.

**Example:**

Input:6Output:3Explanation:The first six elements of the magic string S are "12211", which contains three 1, so it returns 3.

The idea is as follows: summarizing the law, when the subscript i is even, the number of repo[i] corresponding to the number should be 1;

When i is an odd number, the number of repo[i] corresponding to the number shall be 2;

And each time you add, you can simulate 1, 2, 1, 2 with 3-1=2, 3-2=1. . . The change.

The following is the code:

```
class Solution {
public:
int magicalString(int n) {
if(n<1)
return 0;
if(n<=3)
return 1;
vector<int> repo;
repo.push_back(1);
repo.push_back(2);
repo.push_back(2);
long total=3;
int num;
long coun=1;
for(int i=2;total<n;i++){
if(i%2==0){
num=1;
coun+=repo[i];
}
else num=2;
for(int k=0;k<repo[i];k++){
repo.push_back(num);
}
total+=repo[i];
}
if(num==1&&total-n==1)
return coun-1;
return coun;
}
};
```