Medium

Quiz

#481 Magical String

APPROACH

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

1 of 4

1:00

What is the optimal approach for this problem?