Magical String - Practice Coding Problems

Magical String - Problem

A magical string s consists of only '1' and '2' and obeys the following rule:

The string s is magical because concatenating the sequence of lengths of its consecutive groups of identical characters generates the string itself.

For example, the first few elements of the magical string are 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 ......"

Counting the occurrences of 1's or 2's in each group yields the sequence:

"1 2 2 1 1 2 1 2 2 1 2 2 ......"

You can see that concatenating the occurrence sequence gives us s itself.

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

Input & Output

Example 1 — Basic Case

$ Input: n = 6

› Output: 3

💡 Note: Magical string: "122112" → Groups: "1 22 11 2" → First 6 chars have three 1's at positions 0, 3, 4

Example 2 — Small Input

$ Input: n = 1

› Output: 1

💡 Note: First character of magical string is '1', so count is 1

Example 3 — Longer Sequence

$ Input: n = 10

› Output: 5

💡 Note: Magical string: "1221121221" → Contains 5 ones at positions 0, 3, 4, 7, 8

Constraints

1 ≤ n ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Given n = 6, need count of 1s in first 6 characters

Self-Generation

String describes its own group lengths: 1,2,2,1,1,2...

Count Result

First 6 chars '122112' contain 3 ones

Key Takeaway

🎯 Key Insight: The magical string is self-describing - it contains the lengths of its own consecutive character groups

Asked in

G Google 15 f Facebook 8

The key insight is that the magical string describes its own structure through group lengths. We generate the string by reading group lengths from earlier positions and alternating between characters '1' and '2'. Best approach uses simulation with two pointers for clear read/write separation. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Simulation	O(n)	O(n)	Use two pointers to efficiently generate only the needed portion
Count While Generating	O(n)	O(n)	Count 1's during generation without storing entire string
Generate Full String	O(n)	O(n)	Generate the entire magical string up to length n, then count 1's

Two Pointers Simulation — Algorithm Steps

Initialize pointers: read pointer and write pointer
Use read pointer to get next group length
Generate group using write pointer
Advance both pointers appropriately
Stop when we reach n characters and count 1's

Visualization

Tap to expand

Step-by-Step Walkthrough

Setup Pointers

Read pointer for lengths, write pointer for new chars

Generate Groups

Read length, write characters, advance both pointers

Count Result

Count 1s in first n positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>

int solution(int n) {
    if (n == 0) return 0;
    if (n <= 3) return 1; // For n=1,2,3 the answer is always 1
    
    // Initialize the magical string
    int* magic = (int*)malloc(n * sizeof(int));
    magic[0] = 1;
    magic[1] = 2;
    magic[2] = 2;
    
    // Two pointers: read pointer and write pointer
    int readPtr = 2;
    int writePtr = 3;
    
    // Current character alternates between 1 and 2
    int currentChar = 1; // Start with 1 for the 3rd group
    
    while (writePtr < n) {
        // Get group length from read_ptr position
        int groupLength = magic[readPtr];
        
        // Fill the group with currentChar
        for (int i = 0; i < groupLength && writePtr < n; i++) {
            magic[writePtr] = currentChar;
            writePtr++;
        }
        
        // Move to next group: switch character and advance read pointer
        currentChar = (currentChar == 1) ? 2 : 1;
        readPtr++;
    }
    
    // Count 1's in the first n characters
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (magic[i] == 1) count++;
    }
    
    free(magic);
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

We generate exactly n characters with optimized pointer movements

✓ Linear Growth

Space Complexity

O(n)

We still need to store the magical string of length n

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler