main.cpp

// Source: https://leetcode.com/problems/magical-string
// Title: Magical String
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// A magical string `s` consists of only `'1'` and `'2'` and obeys the following rule:
//
// - Concatenating the sequence of lengths of its consecutive groups of identical 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 counting the occurrences of `1`'s or `2`'s in each group yields the sequence`"1 2 2 1 1 2 1 2 2 1 2 2 ......"`.
//
// You can see that concatenating the occurrence sequence gives us`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 <= 10^5`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <algorithm>
#include <cctype>
#include <vector>

using namespace std;

// The first three numbers are "122"
class Solution {
  enum Num { ONE = false, TWO = true };

 public:
  int magicalString(int n) {
    auto s = vector<bool>({ONE, TWO, TWO});
    for (auto i = 2; s.size() < n; ++i) {
      auto next = !s.back();
      s.push_back(next);
      if (s[i] == TWO) s.push_back(next);
    }
    return count(s.begin(), s.begin() + n, ONE);
  }
};