Given a number as a string , find the number of contiguous subsequences which recursively add up to 9 | Java 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
import java . io . * ; class GFG { static int count9s ( String number ) { int count = 0 ; int n = number . length ( ) ; for ( int i = 0 ; i < n ; i ++ ) { int sum = number . charAt ( i ) - '0' ; if ( number . charAt ( i ) == '9' ) count ++ ; for ( int j = i + 1 ; j < n ; j ++ ) { sum = ( sum + number . charAt ( j ) - '0' ) % 9 ; if ( sum == 0 ) count ++ ; } } return count ; } public static void main ( String [ ] args ) { System . out . println ( count9s ( "4189" ) ) ; System . out . println ( count9s ( "1809" ) ) ; } }