Given a number as a string , find the number of contiguous subsequences which recursively add up to 9 | PHP program to count substrings with recursive sum equal to 9 ; To store result ; Consider every character as beginning of substring ; 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 Code
< ? php function count9s ( $ number ) { $ count = 0 ; $ n = strlen ( $ number ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { $ sum = $ number [ $ i ] - '0' ; if ( $ number [ $ i ] == '9' ) $ count ++ ; for ( $ j = $ i + 1 ; $ j < $ n ; $ j ++ ) { $ sum = ( $ sum + $ number [ $ j ] - '0' ) % 9 ; if ( $ sum == 0 ) $ count ++ ; } } return $ count ; } echo count9s ( " 4189 " ) , " STRNEWLINE " ; echo count9s ( " 1809 " ) ; ? >