Table of Contents
Given a string which represent a number, we need to write a function to find the number of sub-strings of the given string that add up to 9.
Examples
a) Input string : 7299
Output : 6
Here, there are 6 substrings which recursively add up to 9
Sub-strings are: 72, 729, 7299, 9, 99, 9
b) Input string : 999
Output : 6
Here, there are 6 substrings which recursively add up to 9
Sub-strings are: 9, 99, 999, 9, 99, 9
Time complexity : O(n2)
Algorithm
1. Store the count of number of substrings in count.
2. Initialize with 0.
3. Consider every character as start of substring, store sum of digits in substring in sum.
4. If current character is 9, increment count.
5. One by one choose all characters next of current character as end of character.
6. Add end character to sum, if sum becomes multiple of 9, increment count. Divide sum with 0(remainder should be 0)
7. Return final count.
C++ Program
#include <bits/stdc++.h>
using namespace std;
//Main function
int main()
{
char string[] = "7299";
//Initialize count = 0
int count = 0;
int length = strlen(string);
for (int i = 0; i < length; i++)
{
int sum = string[i] - '0';
//If char is 9, increment count
if (string[i] == '9')
{
count++;
}
//loop for end char and sum is multiple of 9
//incremnt count
for (int j = i+1; j < length; j++)
{
sum = (sum + string[j] - '0')%9;
if (sum == 0)
{
count++;
}
}
}
//return final count
cout<<"count of sub-strings for 7299 is: "<<count<<endl;
return 0;
}