algoadvance

Leetcode 481. Magical String

Problem Statement

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

• The string is magical because concatenating the number of contiguous occurrences of characters ‘1’ and ‘2’ generates the string itself.

The first few elements of the magical string S is str = “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 the groups are: 1 2 2 1 1 2 1 2 2 1 2 2 …..

You can see that the occurrence sequence above is the same as S.

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

Clarifying Questions

1. Can n be zero or negative?
   • No, according to the problem, n is guaranteed to be a positive integer.
2. Is there an upper limit on n?
   • There is no specific upper limit mentioned, but the solution should handle reasonably large values efficiently.

Strategy

1. Generate the Magical String: Generate at least n characters of the magical string S dynamically.
2. Count ‘1’s in the First n Characters: Once the string is generated up to length n, count the number of ‘1’s in the first n characters.

Code

#include <iostream>
#include <vector>

int magicalString(int n) {
    if (n == 0) return 0;
    if (n <= 3) return 1;
    
    std::vector<int> magical = {1, 2, 2};
    int count_of_ones = 1; // initially, there is one '1' in "122"
    int idx = 2; // start from index 2, considering given initial string "122"
    int num_to_add = 1;
    
    while (magical.size() < n) {
        for (int i = 0; i < magical[idx]; ++i) {
            magical.push_back(num_to_add);
            if (num_to_add == 1 && magical.size() <= n) {
                count_of_ones++;
            }
        }
        num_to_add = (num_to_add == 1) ? 2 : 1;
        idx++;
    }

    return count_of_ones;
}

int main() {
    int n = 6; // example input
    std::cout << "Number of '1's in the first " << n << " characters of the magical string: " << magicalString(n) << std::endl;
    return 0;
}

Time Complexity

• Time Complexity: The solution has a time complexity of O(n) because we iterate through the length of the string only once while generating it.
• Space Complexity: The space complexity is also O(n) due to storing the generated magical string in a vector for up to n characters.

This strategy ensures that the solution is efficient and can handle reasonably large values of n effectively.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• 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?