Watch 10 video solutions for Magical String, a medium level problem involving Two Pointers, String. This walkthrough by Code Crusaders has 2,460 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A magical string s consists of only '1' and '2' and obeys the following rules:
'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 <= 105Problem Overview: The magical string is a sequence consisting only of 1 and 2 where the counts of consecutive groups form the same sequence itself. Starting from "122", each value in the sequence tells how many times the next number should appear. Given n, you need to generate the first n characters of this sequence and return the number of 1s.
Approach 1: Explicit Count Method for Small n (Time: O(n), Space: O(n))
This approach directly builds the magical string using an expandable list. Start with the base sequence [1,2,2]. Maintain a pointer that reads how many times the next value should appear and append that many 1s or 2s to the sequence. After each append operation, flip the next value between 1 and 2. Continue until the sequence length reaches n. Finally, iterate through the first n elements and count the number of 1s. This method is straightforward and easy to reason about, making it useful when implementing quickly during practice. It primarily relies on sequential array expansion and simple iteration over the string-like sequence.
Approach 2: Two-Pointer Simulation Approach (Time: O(n), Space: O(n))
The optimal solution simulates the construction of the magical string using two pointers. One pointer (read) tracks the position that tells how many characters to generate next, while another pointer effectively extends the sequence. Start with [1,2,2] and maintain a variable for the next number to append. For each step, read the count at the read pointer and append that many occurrences of the next number. After generating the values, toggle between 1 and 2 and advance the pointer. While appending, keep a running count of 1s to avoid an extra pass. The algorithm behaves similarly to a classic two pointers simulation where one pointer drives generation and the other grows the sequence.
This technique works because the magical string is self-referential: the sequence itself dictates the lengths of its groups. Instead of recomputing group sizes, you reuse previously generated values through pointer traversal. Each element is processed once, giving linear time complexity. The approach is efficient and predictable since every append operation is directly determined by an earlier value.
Recommended for interviews: The two-pointer simulation approach. It demonstrates that you recognize the self-referential pattern and can model it with controlled sequence generation. Interviewers usually expect the O(n) simulation rather than repeatedly recomputing counts. Implementing the simple explicit construction first shows understanding, while the two-pointer version shows stronger algorithmic control.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Explicit Count Method for Small n | O(n) | O(n) | When implementing a simple simulation or when n is small and readability is preferred |
| Two-Pointer Simulation Approach | O(n) | O(n) | General case and interview settings where efficient sequential generation is expected |