Last updated on July 18th, 2024 at 03:25 am

Here, We see Magical String LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Topics

String

Companies

Google

Level of Question

Medium

Magical String LeetCode Solution

Problem Statement

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 string s itself.

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

1. Magical String Solution C++

class Solution {
public:
    int magicalString(int n) {
       if( n <= 3) return 1;
       string s = "122";
       int i = 2;
       while(s.size() < n)
       {
          if(s[i]=='1')
          {
              if(s[s.size()-1] == '2') s.push_back('1');
              else s.push_back('2');
          }
          else
          {
              if(s[s.size()-1] == '2') s += "11";
              else s += "22";
          }
          i++;
       }
       int cnt = count(s.begin(),s.begin() + n,'1');
       return cnt;
    }
};

2. Magical String Solution Java

class Solution {
    public int magicalString(int n) {
        StringBuilder st=new StringBuilder("122");
        int p1=2,p2=st.length(),count=0;
        while(st.length()<n){
            if(st.charAt(p1)=='1'){
                if(st.charAt(p2-1)=='1')
                    st.append(2);
                else
                    st.append(1);
                p2++;
            }
            else{
                if(st.charAt(p2-1)=='1')
                    st.append(22);
                else
                    st.append(11);
                p2+=2;
            }
            p1++;
        }
        for(int i=0;i<n;i++){
            if(st.charAt(i)=='1')
                count++;
        }
        return count;
    }
}

3. Magical String Solution JavaScript

var magicalString = function(n) {
    const arr = ['1', '2', '2'];
    let i = 0;
    let res = 1;
    while (arr.length < n) {
        let val = i % 2 === 0 ? '1' : '2';
        let isOne = val === '1';
        if (arr[i + 2] === '1') {
            arr.push(val);
            if (isOne) res++;
        } else {
            arr.push(val);
            if (isOne) res++;
            if (arr.length >= n) break;
            arr.push(val);
            if (isOne) res++;
        }
        i++;
    }
    return res;
};

4. Magical String Solution Python

class Solution(object):
    def magicalString(self, n):
        if n == 0:
            return 0
        s = [1, 2, 2]
        i = 2
        while len(s) < n:
            s += [3 - s[-1]] * s[i]
            i += 1
        return s[:n].count(1)