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

Try It