# Beat 91% Java solution

• Thanks to the paper that @StefanPochmann mentioned in his post. Just as Stefan said, all we need is the graph in page 3. It's really impressive.

Below is the code beating 91% in Java, well, I first time wanted to write a recursive solution, but ended with stackoverflow.

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

int[] arr = new int[n + 1];
arr[0] = 1; arr[1] = 2; arr[2] = 2;

int head = 2, tail = 3, val = 1, count = 1;
while (tail < n) {
if (val == 1) count += arr[head];
for (int i = 0; i < arr[head]; i++) {
arr[tail++] = val;
}
val ^= 3;
}
if (arr[n] == 1) count--;
return count;
}
``````

• This doesn't really have anything to do with that paper or my post, though. They're about solving this with only O(log n) space in a different way. What you're doing is just the standard O(n) space solution.

• @StefanPochmann Well, actually I get the idea of solving this question from the graph of that paper... I know your post is about O(logn) space, but what I meant is just the relationship between `1`s and `2`s I got from that graph.

When I first saw this question, actually I have no idea how to do it, and I don't want to search for the right answers from other posts directly, so I read the paper you mentioned. That's all. So this has something to do with that paper, maybe not as advanced as your thought.

• Ah, ok.

Anyway... would be interesting to see an O(log n) space solution in languages other than Python. Maybe in Java it could be done nicely with streams?

• @StefanPochmann Maybe... I am more than happy to see your Java O(logn) solution... :)

You know more about Java than me actually :/

• @StefanPochmann Nice job, man!

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