N different Palindromes - NDIFFPAL CodeChef Easy Question
Hello , everyone !
Lets quickly move on to discuss today's question
Here is the link to the PROBLEM.
So understanding the problem is simple.
We just need to construct a string that has n different palindromes int it.
We can solve this question in many ways , here i will list one of my ways .
So there is a simpler way to solve the problem (discussed at he end) , though i complicated the things just like that .
i took 3 cases , one for n=3k, one for n=3k+1 , one for 3k+2;
Then i took the 26 letters , and started printing the sequence till n/3 then printed some characters in between and then printed from the previous character in reverse order.
I got this trick by counting palindromes and getting the pattern in it .
Here is the code for it :-
I hope you will understand it better through code :-
Code :-
#include <iostream>
using namespace std;
int main() {
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n%3==0)
{
int i=0;
char ch='a';
while(i!=n/3)
{
if(ch!='z')
{
cout<<ch;
ch++;
}
else
{
cout<<ch;
ch='a';
}
i++;
}
if(ch=='a')
{
ch='z';
}
else
{
ch--;
}
while(i!=2*n/3)
{
if(ch!='a')
{
cout<<ch;
ch--;
}
else
{
cout<<ch;
ch='z';
}
i++;
}
cout<<endl;
}
else if(n%3==1)
{
int i=0;
char ch='a';
while(i!=n/3)
{
if(ch!='z')
{
cout<<ch;
ch++;
}
else
{
cout<<ch;
ch='a';
}
i++;
}
cout<<ch;
if(ch=='a')
{
ch='z';
}
else
{
ch--;
}
while(i!=2*n/3)
{
if(ch!='a')
{
cout<<ch;
ch--;
}
else
{
cout<<ch;
ch='z';
}
i++;
}
cout<<endl;
}
else if(n%3==2)
{
int i=0;
cout<<"xy";
char ch='a';
while(i!=n/3)
{
if(ch!='z')
{
cout<<ch;
ch++;
}
else
{
cout<<ch;
ch='a';
}
i++;
}
if(ch=='a')
{
ch='z';
}
else
{
ch--;
}
while(i!=2*(n/3))
{
if(ch!='a')
{
cout<<ch;
ch--;
}
else
{
cout<<ch;
ch='z';
}
i++;
}
cout<<endl;
}
}
// your code goes here
return 0;
}
Let me also give you an alternative easier approach .
We just print out abcdefgh.... continuously as no palindromes arise due to symmetry , the only pallinromes are the trivial ones of lenght one , the letters themselves.
Code :-
#include<stdio.h>
int main()
{
int t,n,i; char str[10001];
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
str[i]='a'+(i%26);
str[n]='\0';
printf("%s\n",str);
}
return 0;
}
Comments
Post a Comment