4-line C++ O(N) solution using queue (detailed explanation)


  • 0

    Algorithm:
    Starting from prefix "122" of magical string S, we use a queue<int> q to store its digits from the second 2 (i.e., S[2]).

    1. Initialize q with a single 2 representing the second 2 of S.
    2. Scan and pop the front of q and push q.front() many of d's into q, where both q.front() and d are 2 and 1 and they alternate each time when scanned.
    3. Repeat Step 2 until the max desired length L == n of the magical string is scanned. Meanwhile, also update digit 1's count ones whenever d == 1.

    Note:

    • d ^= 3 flips d between 1 and 2. You can also use d = 3-d as well.
    • The outer loop has size n-3 and inner loop has max size 2, so O(n) for time complexity.
      int magicalString(int n) {
          int ones = 1; queue<int> q({2});
          for (int L = 3, d = 1; L < n; d ^= 3, q.pop())
            for (int i = 0; i++ < q.front() && L++ < n; q.push(d), ones += d%2) ;
            
          return n? ones : 0;
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.