algoadvance

A magical string S consists of only ‘1’ and ‘2’ and obeys the following rules:

The string is initially “122”. After the first 3 characters, the next character can be constructed by reading the previous characters in the string and appending the corresponding number of ‘1’s or ‘2’s. The rule to expand S is:

• ‘1’ means append 1 ‘2’ to the string.
• ‘2’ means append 2 ‘1’s to the string.

Given an integer n, you need to find the number of ‘1’s in the first n characters of the magical string S.

Clarifying Questions

1. What should be returned if n is 0?
   • Return 0 since there are 0 characters to consider.
2. Are there any constraints on the value of n?
   • Yes, 1 <= n <= 100000.

Once these are clear, we can proceed to the solution.

Strategy

The magical string is constructed following the specified rules. To solve this problem:

1. Start with the initial string “122”.
2. Use two pointers:
   • One (let’s call it pos) to keep track of where we are reading ‘1’ or ‘2’.
   • Another to mark the end of the current string, so we know where to append new characters.
3. According to the character at pos, append 1 or 2 instances of the next alternating character to the string.
4. Continue this process until the length of the string is at least n.
5. Count the number of ‘1’s in the first n characters of the string.

Code

def magicalString(n: int) -> int:
    if n == 0:
        return 0
    if n <= 3:
        return 1 if n == 1 else 1
    
    s = ['1', '2', '2']
    pos = 2  # The position in the string we're reading to generate new parts.
    
    while len(s) < n:
        next_char = '1' if s[-1] == '2' else '2'
        count = int(s[pos])
        s.extend([next_char] * count)
        pos += 1
    
    return s[:n].count('1')

# Example usage:
n = 6
print(magicalString(n))  # should output 3, corresponding to the first 6 characters "122112"

Time Complexity

• The while loop runs until the length of s reaches n, thus it has a complexity of O(n).
• Extending the list and counting characters are linear operations themselves.
• Therefore, the overall time complexity is O(n).

This approach ensures that we efficiently construct the magical string and count the required characters within acceptable time limits even for large values of n.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?