Algorithm
Problem Name: 481. Magical String
A magical string s consists of only '1' and '2' and obeys the following rules:
- The string s is magical because concatenating the number of contiguous occurrences of characters
'1'and'2'generates the stringsitself.
The first few elements of s is s = "1221121221221121122……". If we group the consecutive 1's and 2's in s, it will be "1 22 11 2 1 22 1 22 11 2 11 22 ......" and the occurrences of 1's or 2's in each group are "1 2 2 1 1 2 1 2 2 1 2 2 ......". You can see that the occurrence sequence is s itself.
Given an integer n, return the number of 1's in the first n number in the magical string s.
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
Constraints:
1 <= n <= 105
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const magicalString = function(n) {
const queue = []
let one = true
let count1 = 0
while (n-- > 0) {
queue.shift()
let c = one ? 1 : 2
one = !one
queue.push(c)
count1 += 2 - c
if (queue[0] === 2 && n-- > 0) {
queue.push(c)
count1 += 2 - c
}
}
return count1
}
Input
n = 6
Output
3
#2 Code Example with Python Programming
Code -
Python Programming
class Solution(object):
def magicalString(self, n):
cnt, s, two = 0, "1", True
for i in range(n - 1):
if s[i] == "1":
cnt += 1
s += "2" if two else "1"
else: s += "22" if two else "11"
two = not two
return cnt if n != 1 else 1
Input
n = 6
Output
3