https://leetcode.com/problems/magical-string/

A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules:

The string S is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string S itself.

The first few elements of string S is the following: S = “1221121221221121122……”

If we group the consecutive ‘1’s and ‘2’s in S, it will be:

1 22 11 2 1 22 1 22 11 2 11 22 ……

and the occurrences of ‘1’s or ‘2’s in each group are:

1 2 2 1 1 2 1 2 2 1 2 2 ……

You can see that the occurrence sequence above is the S itself.

Given an integer N as input, return the number of ‘1’s in the first N number in the magical string S.

Note: N will not exceed 100,000.

1 | Example 1: |

#### java

https://discuss.leetcode.com/topic/74917/simple-java-solution-using-one-array-and-two-pointers

Simple Java solution using one array and two pointers

Algorithm:

- Create an int array a and initialize the first 3 elements with 1, 2, 2.
- Create two pointers head and tail. head points to the number which will be used to generate new numbers. tail points to the next empty position to put the new number. Then keep generating new numbers until tail >= n.
- Need to create the array 1 element more than n to avoid overflow because the last round head might points to a number 2.
- A trick to flip number back and forth between 1 and 2: num = num ^ 3

1 | public class Solution { |

https://discuss.leetcode.com/topic/74896/very-straightforward-and-simple-java-solution-o-n

Very Straightforward and simple Java solution O(n)

1 | public int magicalString(int n) { |

https://discuss.leetcode.com/topic/75273/o-log-n-space-java

O(log n) space Java

Based on my Python solution. Here I use a helper class giving me the Kolakoski sequence (that’s its name) one element at a time with its next method. It has the first three elements hard-coded, and after that, it uses another instance of the sequence to iterate further. That other instance does the same, so it might eventually use yet another instance. And so on, O(log n) nested Kolakoski objects iterating in parallel at different speeds as needed. Takes O(log n) space and O(n) time.

1 | public class Solution { |

https://discuss.leetcode.com/topic/75067/simple-java-solution

Simple Java Solution

1 | public int magicalString(int n) { |

#### cpp

https://discuss.leetcode.com/topic/74637/short-c

Short C++

Just build enough of the string and then count.

1 | int magicalString(int n) { |

#### python

https://discuss.leetcode.com/topic/74640/short-python-using-queue

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.

1 | class Solution(object): |

Old version:

1 | class Solution(object): |

https://discuss.leetcode.com/topic/75242/o-log-n-space-using-recursive-generators

O(log n) space using recursive generators

There’s a paper called A Space-Efficient Algorithm for Calculating the Digit Distribution in the Kolakoski Sequence about an O(log n) space and O(n) time algorithm. I didn’t read the paper but wrote my code based on Figure 1 on page 3. I use one generator per level, and to get things going, I hardcode the first three digits caused by the first two digits of the level above (which I therefore ignore).

1 | def magicalString(self, n): |

I think it’s O(log n) space and O(n) time. Here are test results for different n, counting the numbers of generators and yields to measure space and time:

1 | 'test' |

The number of generators is very close to log1.5(n), which makes sense because apparently there are about equally many ones and twos in any prefix of the sequence, so on average one digit in a generator causes 1.5 digits in the generator using it.

The number of yields is very close to 3n, which also makes sense. The outermost generator yields n times, the generator it uses yields about (2/3)n times, the next inner generator yields about (2/3)2n times, and so on. So the total number of yields is about:

n ⋅ ∑i=0..∞ (2/3)i = n ⋅ 1/(1-2/3) = 3n

Here’s the testing code:

1 | import itertools |