Magical String

medium string two pointers

Problem

The magical string s = "12211212212211...". Return the count of 1s in s[0..n-1].

Inputn = 6

Output3

"122112" has three 1s in the first 6 characters.

def magical_string(n):
    if n == 0: return 0
    s = [1, 2, 2]
    p = 2
    while len(s) < n:
        nxt = 3 - s[-1]
        for _ in range(s[p]):
            s.append(nxt)
        p += 1
    return s[:n].count(1)

function magicalString(n) {
  if (n === 0) return 0;
  const s = [1, 2, 2];
  let p = 2;
  while (s.length < n) {
    const nxt = 3 - s[s.length - 1];
    for (let i = 0; i < s[p]; i++) s.push(nxt);
    p++;
  }
  return s.slice(0, n).filter(x => x === 1).length;
}

class Solution {
    public int magicalString(int n) {
        if (n == 0) return 0;
        List s = new ArrayList<>(Arrays.asList(1, 2, 2));
        int p = 2;
        while (s.size() < n) {
            int nxt = 3 - s.get(s.size() - 1);
            for (int i = 0; i < s.get(p); i++) s.add(nxt);
            p++;
        }
        int c = 0;
        for (int i = 0; i < n; i++) if (s.get(i) == 1) c++;
        return c;
    }
}

int magicalString(int n) {
    if (n == 0) return 0;
    vector s = {1, 2, 2};
    int p = 2;
    while ((int)s.size() < n) {
        int nxt = 3 - s.back();
        for (int i = 0; i < s[p]; i++) s.push_back(nxt);
        p++;
    }
    int c = 0;
    for (int i = 0; i < n; i++) if (s[i] == 1) c++;
    return c;
}

Explanation

The magical string is built by a rule that feeds on itself: the string describes the lengths of its own runs of equal digits. Our job is to generate it until it is long enough, then count the 1s.

We start with the known seed [1, 2, 2] and a read pointer p sitting at index 2. The pointer tells us how many copies of the next digit to append.

Each step we compute the next digit by flipping between 1 and 2 with nxt = 3 - s[-1] (so a 1 follows a 2 and vice versa). Then we append it s[p] times — that count comes from reading the string we have already built — and move p forward.

Once the string reaches length n, we just count how many 1s appear in the first n characters with s[:n].count(1).

Example: for n = 6 the string grows to "122112", which has three 1s, so the answer is 3.

Time: O(n) Space: O(n)