I have a naive `O(n)`

algorithm below.

Let's think hard if there is O(1) algorithm. We've seen patterns in the result.

```
public class Solution {
public int magicalString(int n) {
if (n == 0) return 0;
// initialize the string with "122", after "122", the char being considered is surely not part of the newly added segment of the string.
StringBuilder sb = new StringBuilder("122");
int cnt = 0, pos = 2, pre = 2;
while (sb.length() <= n) {
if (sb.charAt(pos) == '1')
// if previously "1" or "11" was appended, this time add "2" or "22".
sb.append(pre == 1 ? "2" : "1");
else sb.append(pre == 1 ? "22" : "11");
pre = pre == 1 ? 2 : 1;
pos++;
}
// Calculate how many 1's in the string builder.
for (int i = 0; i < n; i++)
if (sb.charAt(i) == '1') cnt++;
return cnt;
}
}
```