Given a number as a string , find the number of contiguous subsequences which recursively add up to 9 | Set 2 | C ++ program to count substrings with recursive sum equal to 9 ; to store no . of previous encountered modular sums ; no . of modular sum ( == 0 ) encountered till now = 1 ; if number is 0 increase ; no . of continuous_zero by 1 ; else continuous_zero is 0 ; increase d value of this mod_sum ; subtract no . of cases where there are only zeroes in substring ; 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 ) ; int d [ 9 ] ; memset ( d , 0 , sizeof ( d ) ) ; d [ 0 ] = 1 ; int result = 0 ; int mod_sum = 0 , continuous_zero = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! int ( number [ i ] - '0' ) ) continuous_zero ++ ; else continuous_zero = 0 ; mod_sum += int ( number [ i ] - '0' ) ; mod_sum %= 9 ; result += d [ mod_sum ] ; d [ mod_sum ] ++ ; result -= continuous_zero ; } return result ; } int main ( ) { cout << count9s ( "01809" ) << endl ; cout << count9s ( "1809" ) << endl ; cout << count9s ( "4189" ) ; return 0 ; }