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.
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;
}
};
