Given a number as a string , find the number of contiguous subsequences which recursively add up to 9 | C ++ program to count substrings with recursive sum equal to 9 ; int count = 0 ; To store result ; Consider every character as beginning of substring ; int sum = number [ i ] - '0' ; sum of digits in current substring ; One by one choose every character as an ending character ; Add current digit to sum , if sum becomes multiple of 5 then increment count . Let us do modular arithmetic to avoid overflow for big strings ; driver program to test above function
#include <iostream> NEW_LINE #include <cstring> NEW_LINE using namespace std ; int count9s ( char number [ ] ) { int n = strlen ( number ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( number [ i ] == '9' ) count ++ ; for ( int j = i + 1 ; j < n ; j ++ ) { sum = ( sum + number [ j ] - '0' ) % 9 ; if ( sum == 0 ) count ++ ; } } return count ; } int main ( ) { cout << count9s ( "4189" ) << endl ; cout << count9s ( "1809" ) ; return 0 ; }