leetcode

commit aeea7f6d060313e3d945c34812d03dc511dc71f7
parent 24d08f726dc86d5a07c392b7fe416d67867e706e
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Fri, 31 May 2024 17:35:49 +0200

1 Random Problem

Diffstat:
A
Problems/0481.cpp
 | 
24
++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 25 insertions(+), 0 deletions(-)
diff --git a/Problems/0481.cpp b/Problems/0481.cpp
@@ -0,0 +1,24 @@
+class Solution {
+  public:
+    int magicalString(const int n) const {
+        if (n <= 3) return 1;
+
+        queue<int> q;
+        q.push(2);
+
+        int count = 2, res = 1, last = 2;
+        while (!q.empty()) {
+            const int crnt = q.front();
+            q.pop();
+
+            res += crnt == 1;
+            if (++count == n) return res;
+
+            last = last == 1 ? 2 : 1;
+            for (int i = 0; i < crnt; i++)
+                q.push(last);
+        }
+
+        return -1;
+    }
+};
diff --git a/README.md b/README.md
@@ -351,6 +351,7 @@ for solving problems.
 |  0463  |    Easy    | [Island Perimeter](Problems/0463.cpp)                                                              |
 |  0472  |    Hard    | [Concatenated Words](Problems/0472.cpp)                                                            |
 |  0477  |   Medium   | [Total Hamming Distance](Problems/0477.cpp)                                                        |
+|  0481  |   Medium   | [Magical String](Problems/0481.cpp)                                                                |
 |  0485  |    Easy    | [Max Consecutive Ones](Problems/0485.cpp)                                                          |
 |  0486  |   Medium   | [Reachable Nodes With Restrictions](Problems/0486.cpp)                                             |
 |  0491  |   Medium   | [Non-decreasing Subsequences](Problems/0491.cpp)                                                   |