#481
Magical String
specialist · 870 · lc medium +31 · verified · 54.6% accepted · 377 likes · top 47%
Description
The magical string s uses only '1' and '2' and is self-describing: when you list the lengths of its runs of identical characters, that sequence of lengths reconstructs s itself.
The sequence begins "1221121221221121122...". Grouping it gives "1 22 11 2 1 22 ..." with run lengths 1, 2, 2, 1, 1, 2, ... — and concatenating those lengths reproduces the original string.
Given n, return how many '1' characters appear in the first n positions of the magical string.
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
Code
1
2
3