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.

Examples

Example 1:

1
2
3

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:

1
2

Input: n = 1
Output: 1

Solution

Method 1 - Iteration

To solve the problem of counting the number of ‘1’s in the first n elements of the magical string s, we need to generate the magical string up to the required length and count the ‘1’s.

The magical string s starts with “122”. We will:

  1. Generate the magical string iteratively using the rules described.
  2. Use a pointer to control where to read the number of occurrences (from 1, 2 sequence).
  3. Append the generated characters based on the number of occurrences specified by the pointer.
  4. Count the number of ‘1’s in the first n characters of the string.

Here are the steps in details:

  1. Initialize the magical string with “122”.
  2. Use a pointer to iterate over the sequence and determine how many of each character (‘1’ or ‘2’) to add next.
  3. Alternate between adding ‘1’s and ‘2’s.
  4. Count the ‘1’s in the first n characters once the string reaches or exceeds length n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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

        int[] arr = new int[n + 1];
        arr[0] = 1;
        arr[1] = 2;
        arr[2] = 2;
        
        int head = 2, tail = 3, num = 1, count = 1;
        
        while (tail < n) {
            for (int i = 0; i < arr[head] && tail < n; i++) {
                arr[tail] = num;
                if (num == 1) {
                    count++;
                }
                tail++;
            }
            num = num ^ 3; // Toggle between 1 and 2 (1 ^ 3 = 2, 2 ^ 3 = 1)
            head++;
        }
        
        return count;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def magicalString(self, n: int) -> int:
        if n <= 0: return 0
        if n <= 3: return 1

        s: List[int] = [1, 2, 2]
        head: int = 2
        num: int = 1
        count: int = 1  # Initial 1 is considered in the first 3 characters

        while len(s) < n:
            s.extend([num] * s[head])
            if num == 1:
                count += s[head]
            num = 2 if num == 1 else 1
            head += 1

        return count - (len(s) - n if len(s) > n else 0)

Complexity

  • ⏰ Time complexity: O(n). We generate and check each character up to the required length n.
  • 🧺 Space complexity: O(n),due to the storage of the generated magical string.