Leetcode 481 Solution

This article provides solution to leetcode question 481 (magical-string)
Categories:
Tags:
Access this page by simply typing in "lcs 481" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/magical-string

Solution

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

        vector<int> a;

        a.push_back(1);
        a.push_back(2);
        a.push_back(2);

        int i = 2;
        while (a.size() < n)
        {
            int next = 3 - a.back();

            if (a[i] == 1)
            {
                a.push_back(next);
                i++;
            }
            else if (a[i] == 2)
            {
                a.push_back(next);
                a.push_back(next);
                i++;
            }
        }

        int cnt = 0;
        for (int i = 0; i < n; i++)
            cnt += a[i] == 1;
        return cnt;
    }
};