We’re preparing your current view and syncing the latest data.
A magical string s consists of only '1' and '2' and obeys the following rules: the string is constructed such that the grouping of consecutive '1's and '2's forms the string itself. More specifically, the string s is magical if and only if when grouped by consecutive occurrences of each character, the lengths of these groups form the string s itself. The string s starts with "1 2 2" and the process continues infinitely. Given an integer n, return the number of '1's in the first n numbers in the magical string s.
An integer n representing the length of the magical string to consider.
An integer representing the number of '1's in the first n characters of the magical string.
1 <= n <= 10^5
Example 1
Input
6
Output
3
Explanation
The magical string starts with "1 2 2 1 1 2". There are three '1's in the first 6 characters.