481. Magical String

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
2
3
4
Example 1:
Input: 6
Output: 3
Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.

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:

  1. Create an int array a and initialize the first 3 elements with 1, 2, 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.
  3. Need to create the array 1 element more than n to avoid overflow because the last round head might points to a number 2.
  4. A trick to flip number back and forth between 1 and 2: num = num ^ 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public int magicalString(int n) {
if (n <= 0) return 0;
if (n <= 3) return 1;

int[] a = new int[n + 1];
a[0] = 1; a[1] = 2; a[2] = 2;
int head = 2, tail = 3, num = 1, result = 1;

while (tail < n) {
for (int i = 0; i < a[head]; i++) {
a[tail] = num;
if (num == 1 && tail < n) result++;
tail++;
}
num = num ^ 3;
head++;
}

return result;
}
}

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

Very Straightforward and simple Java solution O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int magicalString(int n) {
StringBuilder magic = new StringBuilder("1221121221221121122");
int pt1 = 12, pt2 = magic.length(), count = 0; //initiate pointers
//generate sequence directly
while(magic.length() < n){
if(magic.charAt(pt1) == '1'){
if(magic.charAt(pt2-1) == '1') magic.append(2);
else magic.append(1);
pt2++;
}else{ //==2
if(magic.charAt(pt2-1) == '1') magic.append(22);
else magic.append(11);
pt2+=2;
}
pt1++;
}
for(int i=0;i<n;i++)
if(magic.charAt(i)=='1') count++;
return count;
}

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {

public int magicalString(int n) {
Kolakoski kolakoski = new Kolakoski();
int ones = 0;
while (n-- > 0)
if (kolakoski.next() == 1)
ones++;
return ones;
}

private class Kolakoski {
private int[] queue = {1, 2, 2};
private int first = 0, last = 2;
private Kolakoski source;
int next() {
if (first > last) {
if (source == null) {
source = new Kolakoski();
source.next();
source.next();
}
int output = queue[last % 3] ^ 3;
for (int k = source.next(); k > 0; k--)
queue[++last % 3] = output;
}
return queue[first++ % 3];
}
}
}

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

Simple Java Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int magicalString(int n) {
if(n==0)return 0;
if(n==1)return 1;
StringBuilder sb= new StringBuilder(n);
sb.append("122");
int count=1;
int i=2;
while (sb.length()<n){
if(sb.charAt(i)=='1'){
boolean one=sb.charAt(sb.length()-1) =='1';
count+=one ? 0: 1;
sb.append(one ? 2 : 1);
}else{
boolean one=sb.charAt(sb.length()-1) =='1';
count+=one ? 0: 2;
sb.append(one ? 22 : 11);
}
i++;
}
if(sb.length()>n && sb.charAt(sb.length()-1)=='1')count--;
return count;
}

cpp


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

Short C++

Just build enough of the string and then count.

1
2
3
4
5
6
7
int magicalString(int n) {
string S = "122";
int i = 2;
while (S.size() < n)
S += string(S[i++] - '0', S.back() ^ 3);
return count(S.begin(), S.begin() + n, '1');
}

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
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
S = [1,2,2]
idx = 2
while len(S) < n:
S += S[idx] * [(3 - S[-1])]
idx += 1
return S[:n].count(1)

Old version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
queue = collections.deque([2])
S = [1,2,2]
while len(S) < n:
k = queue.popleft()
tmp = 3 - S[-1]
for i in range(k):
S.append(tmp)
queue.append(tmp)
return S[:n].count(1)

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
2
3
4
5
6
7
8
9
def magicalString(self, n):
def gen():
for x in 1, 2, 2:
yield x
for i, x in enumerate(gen()):
if i > 1:
for _ in range(x):
yield i % 2 + 1
return sum(x & 1 for x in itertools.islice(gen(), 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
2
3
4
5
6
7
8
9
10
11
12
'test'
n generators yields
(=space) (=time)
1 1 1
10 4 25
100 10 295
1000 16 3001
10000 22 30028
100000 27 299935
1000000 33 2999958
10000000 39 29999888
100000000 44 300001534

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import itertools

class Solution(object):
def magicalString(self, n):
def gen():
global generators, yields
generators += 1
for x in 1, 2, 2:
yields += 1
yield x
for i, x in enumerate(gen()):
if i > 1:
for _ in range(x):
yields += 1
yield i % 2 + 1
return sum(x & 1 for x in itertools.islice(gen(), n))

print ' n generators yields'
print ' (=space) (=time)'
for e in range(9):
n = 10**e
generators = yields = 0
Solution().magicalString(n)
print '%10d' * 3 % (n, generators, yields)

谢谢你,可爱的朋友。