In this Leetcode Magical String problem solution Given an integer n, return the largest palindromic integer that can be represented as the product of two n-digits integers. Since the answer can be very large, return it modulo 1337.

Leetcode Magical String problem solution


Problem solution in Python.

class Solution(object):
    def magicalString(self, n):
        """
        :type n: int
        :rtype: int
        """
        q = collections.deque()
        mask = 1 ^ 2
        cnt, num, res = 0, 1, 0
        for _ in range(n):
            q.append(num)
            res += num == 1
            cnt += 1
            if cnt == q[0]:
                q.popleft()
                cnt = 0
                num ^= mask
        return res


Problem solution in Java.

class Solution {
    public int magicalString(int n) {
      
        int[] A = new int[n+2];
        
        int fast=1;
        int slow=1;
        int num= 1;

        while(fast<=n){
            A[fast++] = num; 
            if (A[slow++]==2){
                A[fast++] = num;
            }
            num = 3-num;
        }
     
        int count=0;
        for(int j=1;j<=n;j++){
            if(A[j]==1)
                count++;
        }
        return count;            
        
    }
}


Problem solution in C++.

class Solution {
public:
    int magicalString(int n) {
        if(n<=0)
            return 0; // has 0 1's 
        if(n<=3)
            return 1; // has one 1's 
        int count =0; 
        vector<int> _string;
        _string.push_back(1);
        _string.push_back(2);
        _string.push_back(2);
        int idx = 2;   // the last digit index , decides how many digits will be added to the end of the string  
        int digit = 1;
        while(_string.size()<n){
            if(_string[idx]==1){
                _string.push_back(digit);
            }
            if(_string[idx]==2){
                _string.push_back(digit);
                _string.push_back(digit);
            }
            if(digit==1) digit = 2;
            else digit =1;
            idx++;
        }
        for(int x = 0; x<n; x++){
            if(_string[x]==1)
                count++;    // Counting only till the n specified in the question
        }
        return count;
    }
};