Meeta’s uncle came to visit her in the summer vaccations they brought a lot of chocolates for her but for each chocolate they asked her to give answer to his question. He would give a number as a string, for which Meeta has to find the number of substrings (or contiguous subsequences) of the given string which recursively add up to 9.
The problem is to find out the number of substrings (or contiguous subsequences) of the given string which recursively add up to 9.
All digits of a number recursively add up to 9, if only if the number is multiple of 9. We basically need to check for s%9 for all substrings s.
#include<stdio.h>
#include<string.h>
int count(char * str)
{
int i,j,n,sum,cnt;
sum=0;
n=strlen(str);
cnt=0;
for(i=0;i<n;i++)
{
if(str[i]==‘9’)
cnt++;
sum=str[i]-‘0’;
for(j=i+1;j<n;j++)
{
sum=(sum+str[j]-‘0’);
if(sum!=0&&sum%9==0)
cnt++;
}
}
return cnt;
}
int main()
{
int cnt,t;
char string[20];
scanf("%d",&t);
while(t–)
{
scanf("%s",&string);
cnt=count(string);
printf("%d\n",cnt);
}
return 0;
}