Count how many 1s appear in the first characters of a self-describing binary string.
Problem
A magical string is a binary sequence made only of 1 and 2 that starts with:
clike
1221121221221121122...It has a special property: if you read the sequence in groups of identical digits, the lengths of those groups are themselves the same sequence, written as digits.
For example, the beginning above can be grouped as:
12211212212211- ...
The group lengths are 1, 2, 2, 1, 1, 2, 1, 2, 2, ..., which reproduces the sequence.
Given an integer n, return how many 1s appear in the first n characters of the magical string.
Notes
- The sequence is infinite.
- The answer is based only on the prefix of length
n. - You do not need to generate the entire infinite string.
Input Format
- A single integer
n.
Output Format
- Return the number of
1characters in the firstncharacters of the magical string.
Constraints
- The magical string contains only the digits
1and2.
Example 1
Input
n = 6
Output
3
Explanation
The first 6 characters are 122112, which contains three 1s.
Example 2
Input
n = 1
Output
1
Explanation
The first character is 1, so the count is 1.
Show 1 more example
Example 3
Input
n = 10
Output
5
Explanation
The first 10 characters are 1221121221, which contains five 1s.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.