# Magical String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/magical-string)
Canonical: https://scaleengineer.com/dsa/problems/magical-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
---
## Problem
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 `s` is `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 is `s` itself.

Given an integer `n`, return the number of `1`'s in the first `n` number in the magical string `s`.

**Example 1:**

**Input:** n = 6
**Output:** 3
**Explanation:** The first 6 elements of magical string s is "122112" and it contains three 1's, so return 3.

**Example 2:**

**Input:** n = 1
**Output:** 1

**Constraints:**

* `1 <= n <= 105`

# Approaches
## Two-Pass Simulation
This approach first simulates the generation of the magical string up to the required length `n`. After the string is fully constructed in an array, it performs a second, separate pass over the array to count the number of '1's. This method separates the logic of generation and counting into two distinct steps.
**Time:** O(n) - The generation process involves a single pass where pointers move from left to right, taking O(n) time. The subsequent counting pass also takes O(n) time. Thus, the total time complexity is O(n) + O(n) = O(n). · **Space:** O(n) - We use an array of size `n` to store the generated magical string.
**Pros:** The logic is straightforward and easy to follow because the generation and counting phases are separate.; Implementation is relatively simple.
**Cons:** Slightly less efficient due to requiring two separate passes over the data (one for generation, one for counting).; The generation logic might fill the array slightly beyond what's strictly necessary if the last group of numbers extends past index `n-1`.
### Explanation
The fundamental idea is to build the magical string `s` by following its self-referential rule. We use two pointers: a `readPtr` that indicates which element of `s` to use as the next count, and a `writePtr` that indicates where to place the next generated number. We begin with the known prefix `s = "122"`. The `readPtr` starts at index 2, because the counts for the first two groups (`s[0]=1` and `s[1]=2`) have already been 'used' to form `"1"` and `"22"`. The `writePtr` starts at index 3. The number to be written, `num`, alternates between 1 and 2. In a loop, we read the count `c = s[readPtr]`, append `num` to the string `c` times, flip `num`, and advance `readPtr`. This continues until we have generated at least `n` characters. Finally, a simple iteration through the first `n` elements of the generated string yields the count of '1's.

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

        int[] s = new int[n];
        s[0] = 1;
        s[1] = 2;
        s[2] = 2;

        int readPtr = 2;
        int writePtr = 3;
        int num = 1;

        while (writePtr < n) {
            int count = s[readPtr];
            for (int i = 0; i < count; i++) {
                if (writePtr < n) {
                    s[writePtr] = num;
                    writePtr++;
                } else {
                    break;
                }
            }
            num = 3 - num; // Flip between 1 and 2
            readPtr++;
        }

        int onesCount = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 1) {
                onesCount++;
            }
        }
        return onesCount;
    }
}
```
### Algorithm
1. Handle the base cases. If `n` is 0, return 0. If `n` is 1, 2, or 3, the string prefix is `"1"`, `"12"`, or `"122"` respectively, and the count of ones is 1.
2. Create an integer array `s` of size `n` to store the magical string.
3. Initialize the first three elements: `s[0] = 1`, `s[1] = 2`, `s[2] = 2`.
4. Initialize a `readPtr` to 2 (to read the counts), a `writePtr` to 3 (to write new numbers), and a variable `num` to 1 (the next number to be written).
5. Start a loop to generate the string until its length is `n`. The loop continues as long as `writePtr < n`.
6. Inside the loop, read the count from `s[readPtr]`. This count determines how many times `num` should be appended.
7. Append `num` to the array `s` for `count` times, ensuring not to write past the `n`-th position.
8. After appending, flip `num` from 1 to 2 or vice-versa (e.g., `num = 3 - num`).
9. Increment `readPtr` to move to the next count.
10. After the generation loop completes, the array `s` contains the first `n` elements of the magical string.
11. Perform a second pass over the array `s` from index 0 to `n-1`.
12. Count all occurrences of the number 1 and return the total.

## One-Pass Simulation
This optimized approach integrates the counting of '1's directly into the string generation process. Instead of waiting to generate the entire string prefix, it keeps a running total of the '1's encountered. This eliminates the need for a second pass, making the solution more efficient in terms of constant factors and operations.
**Time:** O(n) - The algorithm iterates through the string generation process exactly once. Both the read and write pointers traverse up to `n`, resulting in a linear time complexity. · **Space:** O(n) - An array of size `n` is required to store the state of the magical string as it's being generated.
**Pros:** Highly efficient as it solves the problem in a single pass.; Avoids any redundant computations by stopping as soon as the `n`-th character is processed.
**Cons:** The code can be slightly less readable as the generation and counting logic are intertwined within the same loop.
### Explanation
The generation mechanism is the same as the two-pass approach, utilizing `readPtr` and `writePtr` to extend the string from its initial state of `"122"`. However, this method introduces a counter variable, `onesCount`, initialized to 1. As we generate each new number and are about to place it into our array `s`, we check if the number is a '1'. If it is, and we are still within the first `n` characters (i.e., `writePtr < n`), we increment `onesCount`. The process of generation and counting stops precisely when we have processed `n` characters, ensuring no work is wasted. This single-pass method is more efficient as it combines two steps into one, reducing overhead.

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

        int[] s = new int[n];
        s[0] = 1;
        s[1] = 2;
        s[2] = 2;

        int readPtr = 2;
        int writePtr = 3;
        int num = 1;
        int onesCount = 1;

        while (writePtr < n) {
            int count = s[readPtr];
            for (int i = 0; i < count; i++) {
                if (writePtr < n) {
                    if (num == 1) {
                        onesCount++;
                    }
                    s[writePtr] = num;
                    writePtr++;
                } else {
                    break;
                }
            }
            num = 3 - num; // Flip between 1 and 2
            readPtr++;
        }
        return onesCount;
    }
}
```
### Algorithm
1. Handle the base cases: return 0 for `n <= 0` and 1 for `n <= 3`.
2. Create an integer array `s` of size `n` to store the string.
3. Initialize the first three elements: `s[0] = 1`, `s[1] = 2`, `s[2] = 2`.
4. Initialize a counter for ones, `onesCount`, to 1 (for the first '1' in the string).
5. Initialize `readPtr = 2`, `writePtr = 3`, and `num = 1`.
6. Start a loop that continues as long as `writePtr < n`.
7. Inside the loop, get the count from `s[readPtr]`.
8. Start an inner loop to append `num` for `count` times.
9. In this inner loop, before appending, check if `writePtr` is still less than `n`. If it is, and if `num` is 1, increment `onesCount`.
10. Then, place `num` at `s[writePtr]` and increment `writePtr`.
11. If `writePtr` reaches `n`, break out of the inner loop.
12. After the inner loop, flip `num` (e.g., `num = 3 - num`) and increment `readPtr`.
13. Once the main loop terminates (when `writePtr` is no longer less than `n`), return `onesCount`.

# Solutions
### Java

```java
class Solution { public int magicalString ( int n ) { List < Integer > s = new ArrayList <>( Arrays . asList ( 1 , 2 , 2 )); for ( int i = 2 ; s . size () < n ; ++ i ) { int pre = s . get ( s . size () - 1 ); int cur = 3 - pre ; for ( int j = 0 ; j < s . get ( i ); ++ j ) { s . add ( cur ); } } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( s . get ( i ) == 1 ) { ++ ans ; } } return ans ; } }
```

### Python

```python
class Solution : def magicalString ( self , n : int ) -> int : s = [ 1 , 2 , 2 ] i = 2 while len ( s ) < n : pre = s [ - 1 ] cur = 3 - pre s += [ cur ] * s [ i ] i += 1 return s [: n ]. count ( 1 )
```

### CPP

```cpp
class Solution { public: int magicalString ( int n ) { vector < int > s = { 1 , 2 , 2 }; for ( int i = 2 ; s . size () < n ; ++ i ) { int pre = s . back (); int cur = 3 - pre ; for ( int j = 0 ; j < s [ i ]; ++ j ) { s . emplace_back ( cur ); } } return count ( s . begin (), s . begin () + n , 1 ); } };
```