Scale Engineer

Magical String

Med
#0468Time: 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.
Patterns
Two Pointers
Data structures
String

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

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

Complexity

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.

Trade-offs

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.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem