# 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`
``````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;
}

return result;
}
}
``````

• To flip `x` between any two given values `x1` and `x2`, I think using `x = x1 + x2 - x` is more straightforward (as long as no overflow).

• @zzg_zzm Yes, that is a more general approach. Thanks!

• @shawngao In what way more general?

• @StefanPochmann They way @zzg_zzm described, `x = x1 + x2 - x`, if we know x1 + x2 won't overflow.

• @StefanPochmann They way @zzg_zzm described, `x = x1 + x2 - x`, if we know x1 + x2 won't overflow.

I think @StefanPochmann means `x ^= (x1^x2)` can achieve the same purpose still using `^` operator. So rewriting `3 = 1^2` is more general :-)

• @zzg_zzm yep, agreed. thanks.

• You can just put a tail < n in the for's condition

``````public class Solution {
public int magicalString(int n) {
if (n <= 0) {
return 0;
}
if (n <= 3) {
return 1;
}

int[] a = new int[n];
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] && tail < n; i++) {
a[tail] = num;
if (num == 1) {
result++;
}
tail++;
}
num = num ^ 3;
}

return result;
}
}``````

• why must start 1,2,2?

I wonder whether there is magical string start from 2,2,1,1,2,1,2,2...

• why must start 1,2,2?

I wonder whether there is magical string start from 2,2,1,1,2,1,2,2...

I got your point. Actually, the magic string `S` is uniquely determined by only the first char `S[0]` (either `'1'` or `'2'`). Either case gives a well defined problem, but they are "logically" duplicated problem, so OJ just simply picked the case `S[0] = 1` to define as magic string. The method to solve "the other" magic string will be duplicated anyway.

Hopefully, it will help.

• Good post, I like the idea to represent the characters with int array, and flip between 1 and 2 with XOR. x = x1 + x2 - x is also very good idea.

As I want to avoid the nested loop, I used the algorithm below:

``````int magicalNaive (int n) {
string magical;
magical.append("122");
char next = '1';
/* the position in magical that act as a recurrence count */
int cntIdx = 2;
int cnt = 2;
/* '1' count in magical string */
int ret = 1;
for (int i = 3; i < n; i++) {
if (cnt == 0) {
cnt = magical[++cntIdx] - '0';
next = next == '1' ? '2' : '1';
}

/* push in next to magical top */
ret += next == '1';

magical.push_back (next);
cnt--;
}

return n < 1 ? 0 : ret;
}
``````

• My solution is naive: https://en.wikipedia.org/wiki/Kolakoski_sequence
Using a pointer to point the repeat times number. If it is 1, no repeat, if it is 2, add two repeat number to the result list.

1 and 2 are appear one by one, so using `num = num ^ 3`.

``````    public int magicalString(int n) {
List<Integer> nums = new ArrayList();
int repIndex = 2, i = 3, num = 1, res = 0;
while(i < n){
int repeat = nums.get(repIndex);
repIndex++;
if(repeat == 1) {
i++;
} else {
i += 2;
}
num ^= 3;
}

for(i = 0; i < n; i++){
if(nums.get(i) == 1) res++;
}
return res;
}

}

}``````

• Similar idea, one loop

``````public int magicalString(int n) {
if(n == 0) return 0;

StringBuilder sb = new StringBuilder("122");
int sPtr = 2, groupPtr=2, count = 1;
int nextChar = 1;

while(sPtr < n) {
sb.append(nextChar);
sPtr++;
if(sb.charAt(groupPtr) == '2') {
sb.append(nextChar);
sPtr++;
}
if(nextChar == 1) {
if(sPtr < n) count+=1;
if(sb.charAt(groupPtr) == '2' && sPtr-1 < n)  count+=1;
}
nextChar = nextChar ^ 3;
groupPtr++;
}
return count;
}
``````

• No need to use O(n) space, just keep a window of numbers you will concern.
But still, brilliant solution of yours!

``````    public int magicalString(int n) {
if(n==0)return 0;
int res=1,count=3;
list.offer(2);
while(count<n){
int next = (list.peekLast()==1?2:1);
int occur = list.removeFirst();
for(int i=1;i<=occur&&count<n;i++){
if(next==1)res++;
count++;
}
}
return res;
}
``````

• No need to use O(n) space

Yours does, too.

• @ManuelP That's true, but less.

• 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.

I hate Advanced Math.... I know it's Kolakoski sequence but I still don't know what's the trick to generating the next number.

I draw a graph:

``````            1    2    2    X    M
tail:                      ^
``````

Why will the X be 1 if we don't know what the M is?

• @zzg_zzm

Thanks for your clarification butI still don't get why string S is determined by the first char S[0].....And how it will be a "logically" duplicated.... Sorry about my bad math...

• Improve Space Complexity with Deque.

``````  public int magicalString(int n) {
if(n <= 0){
return 0;
}
if(n <= 3){
return 1;
}

Deque<Integer> que = new ArrayDeque<>(Arrays.asList(2));
int res = 1;
int len = 2;

int nextNum = 1;

while(len < n){
int curNum = que.removeFirst();
if(curNum == 1){
res++;
}
len++;

for(int i = 0; i < curNum; i++){
}
nextNum = nextNum ^ 3;
}

return res;
}``````

• Improve Space Complexity with Deque.

How much does it improve?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.