https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem
Explanation:
ex: aabbcc
then a occurs 2 times
b occurs 2 times and
c occurs 2 times
max of 2,2,2 is 2
min of 2,2,2 is 2
so if max == min then "YES"
ex: aaabbcc
then a occurs 3 times
b occurs 2 times and
c occurs 2 times
max of 3,2,2 is 3
min of 3,2,2 is 2
here max value is 3 and 3 occurred only once
so if max -min == 1 and maxcount == 1 then "YES"
ex: aabbc
then a occurs 2 times
b occurs 2 times and
c occurs 1 times
max of 2,2,1 is 2
min of 2,2,1 is 1
here min value 1 occurred only once
if min == 1 and mincount == 1 then "YES"
BUT
ex: aaabbc
then a occurs 3 times
b occurs 2 times and
c occurs 1 times
max of 3,2,1 is 3
min of 3,2,1 is 1
here min value 1 occurred only once but here answer must be "NO"
so we need to find second maximum and if second maximum is equal to minimum then the answer is "YES"
so
if min == 1 and mincount == 1 and secondmaximum == min then "YES"
Program
#include<stdio.h>
#include<limits.h>
int main()
{
char st[100000];
scanf("%s",&st);
int smax=0,max=INT_MIN,smin=INT_MAX,min =INT_MAX,i,a[26]={0},c1=0,c2=0;
for(i=0;st[i]!='\0';i++)
a[st[i]-'a']++;
for(i=0;i<26;i++)
{
if(a[i]!=0)
{
if(a[i]==max)
c1++;
else if(a[i]> max)
{
c1=1;
smax=max;
max=a[i];
}
else if (a[i]>smax && a[i]<max)
smax=a[i];
if(a[i]==min)
c2++;
else if(a[i]< min)
{
c2=1;
min=a[i];
}
}
}
if(max == min)
printf("YES");
else if((max - min == 1 && c1 == 1)|| (min == 1 && c2 == 1&& smax == min))
printf("YES");
else
printf("NO");
}
Explanation:
ex: aabbcc
then a occurs 2 times
b occurs 2 times and
c occurs 2 times
max of 2,2,2 is 2
min of 2,2,2 is 2
so if max == min then "YES"
ex: aaabbcc
then a occurs 3 times
b occurs 2 times and
c occurs 2 times
max of 3,2,2 is 3
min of 3,2,2 is 2
here max value is 3 and 3 occurred only once
so if max -min == 1 and maxcount == 1 then "YES"
ex: aabbc
then a occurs 2 times
b occurs 2 times and
c occurs 1 times
max of 2,2,1 is 2
min of 2,2,1 is 1
here min value 1 occurred only once
if min == 1 and mincount == 1 then "YES"
BUT
ex: aaabbc
then a occurs 3 times
b occurs 2 times and
c occurs 1 times
max of 3,2,1 is 3
min of 3,2,1 is 1
here min value 1 occurred only once but here answer must be "NO"
so we need to find second maximum and if second maximum is equal to minimum then the answer is "YES"
so
if min == 1 and mincount == 1 and secondmaximum == min then "YES"
Program
#include<stdio.h>
#include<limits.h>
int main()
{
char st[100000];
scanf("%s",&st);
int smax=0,max=INT_MIN,smin=INT_MAX,min =INT_MAX,i,a[26]={0},c1=0,c2=0;
for(i=0;st[i]!='\0';i++)
a[st[i]-'a']++;
for(i=0;i<26;i++)
{
if(a[i]!=0)
{
if(a[i]==max)
c1++;
else if(a[i]> max)
{
c1=1;
smax=max;
max=a[i];
}
else if (a[i]>smax && a[i]<max)
smax=a[i];
if(a[i]==min)
c2++;
else if(a[i]< min)
{
c2=1;
min=a[i];
}
}
}
if(max == min)
printf("YES");
else if((max - min == 1 && c1 == 1)|| (min == 1 && c2 == 1&& smax == min))
printf("YES");
else
printf("NO");
}
Can you please explain it!
ReplyDeleteexplanation of logic to solve the problem is already explained with examples above...in the program i have use the logic to find second maximum...by looking at the if conditions you will be able to understand
Delete