{x}
blog image

Magical String

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

481. Magical String

Description

A magical string s consists of only '1' and '2' and is generated by concatenating the number of contiguous occurrences of characters '1' and '2'. The first few elements of s are "1221121221221121122...". Given an integer n, return the number of '1's in the first n numbers in s.

Solution: Simulate the Construction Process

This solution simulates the generation of the magical string up to length n and counts the number of '1's. The core idea is to iteratively extend the string based on the rules defined in the problem description.

Algorithm:

  1. Initialization: Start with the initial part of the magical string s = [1, 2, 2]. Maintain a pointer i to track the next digit to use for determining the length of the next sequence. i starts at 2.

  2. Iteration: While the length of s is less than n:

    • Get the last digit pre from s.
    • The next digit cur is the opposite of pre (3 - pre).
    • Append cur to s s[i] times (the digit at index i in s determines how many times the cur digit is appended).
    • Increment i.

  3. Counting '1's: After the loop, count the number of '1's in the first n elements of s.

Time Complexity: O(n). The loop iterates at most linearly with respect to n. Appending to the list in Python might be amortized O(1), but in other languages like Java, it could be O(n) in the worst case if resizing is needed often. However, the overall time complexity still remains linear.

Space Complexity: O(n). The string s can grow up to size n in the worst case.

Code Implementation (Multiple Languages)

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.extend([cur] * s[i])  # Efficient extension using extend()
            i += 1
        return s[:n].count(1)

Java

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

C++

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

JavaScript

/**
 * @param {number} n
 * @return {number}
 */
var magicalString = function(n) {
    let s = [1, 2, 2];
    let i = 2;
    while (s.length < n) {
        let pre = s[s.length - 1];
        let cur = 3 - pre;
        for (let j = 0; j < s[i]; j++) {
            s.push(cur);
        }
        i++;
    }
    let count = 0;
    for (let j = 0; j < n; j++) {
        if (s[j] === 1) count++;
    }
    return count;
};

Go

func magicalString(n int) int {
	s := []int{1, 2, 2}
	i := 2
	for len(s) < n {
		pre := s[len(s)-1]
		cur := 3 - pre
		for j := 0; j < s[i]; j++ {
			s = append(s, cur)
		}
		i++
	}
	count := 0
	for _, v := range s[:n] {
		if v == 1 {
			count++
		}
	}
	return count
}

This detailed explanation and multi-language code examples provide a comprehensive solution to the Magical String problem. Remember to consider the potential space complexity implications of list appending in different languages when dealing with very large values of n.