Given a number as a string, write a function to find the number of substrings (or contiguous subsequences) of the given string which recursively add up to 9.
For example digits of 729 recursively add to 9,
7 + 2 + 9 = 18
Recur for 18
1 + 8 = 9
Examples:
Input: 4189 Output: 3 There are three substrings which recursively add to 9. The substrings are 18, 9 and 189. Input: 999 Output: 6 There are 6 substrings which recursively add to 9. 9, 99, 999, 9, 99, 9
All digits of a number recursively add up to 9, if only if the number is multiple of 9. We basically need to check for s%9 for all substrings s. One trick used in below program is to do modular arithmetic to avoid overflow for big strings.
Following is a simple implementation based on this approach. The implementation assumes that there are no leading 0’s in input number.
C++
// C++ program to count substrings with recursive sum equal to 9 #include <iostream> #include <cstring> using namespace std; int count9s( char number[]) { int count = 0; // To store result int n = strlen (number); // Consider every character as beginning of substring for ( int i = 0; i < n; i++) { int sum = number[i] - '0' ; //sum of digits in current substring if (number[i] == '9' ) count++; // One by one choose every character as an ending character for ( int j = i+1; j < n; j++) { // 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 sum = (sum + number[j] - '0' )%9; if (sum == 0) count++; } } return count; } // driver program to test above function int main() { cout << count9s( "4189" ) << endl; cout << count9s( "1809" ); return 0; } |
Java
// Java program to count // substrings with // recursive sum equal to 9 import java.io.*; class GFG { static int count9s(String number) { // To store result int count = 0 ; int n = number.length(); // Consider every character // as beginning of substring for ( int i = 0 ; i < n; i++) { // sum of digits in // current substring int sum = number.charAt(i) - '0' ; if (number.charAt(i) == '9' ) count++; // One by one choose // every character as // an ending character for ( int j = i + 1 ; j < n; j++) { // 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 sum = (sum + number.charAt(j) - '0' ) % 9 ; if (sum == 0 ) count++; } } return count; } // Driver Code public static void main (String[] args) { System.out.println(count9s( "4189" )); System.out.println(count9s( "1809" )); } } // This code is contributed // by anuj_67. |
Python 3
# Python 3 program to count substrings # with recursive sum equal to 9 def count9s(number): count = 0 # To store result n = len (number) # Consider every character as # beginning of substring for i in range (n): # sum of digits in current substring sum = ord (number[i]) - ord ( '0' ) if (number[i] = = '9' ): count + = 1 # One by one choose every character # as an ending character for j in range (i + 1 , n): # 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 sum = ( sum + ord (number[j]) - ord ( '0' )) % 9 if ( sum = = 0 ): count + = 1 return count # Driver Code if __name__ = = "__main__" : print (count9s( "4189" )) print (count9s( "1809" )) # This code is contributed by ita_c |
C#
// C# program to count // substrings with // recursive sum equal to 9 using System; class GFG { static int count9s(String number) { // To store result int count = 0; int n = number.Length; // Consider every character // as beginning of substring for ( int i = 0; i < n; i++) { // sum of digits in // current substring int sum = number[i] - '0' ; if (number[i] == '9' ) count++; // One by one choose // every character as // an ending character for ( int j = i + 1; j < n; j++) { // 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 sum = (sum + number[j] - '0' ) % 9; if (sum == 0) count++; } } return count; } // Driver Code public static void Main () { Console.WriteLine(count9s( "4189" )); Console.WriteLine(count9s( "1809" )); } } // This code is contributed // by anuj_67. |
PHP
<?php // PHP program to count substrings // with recursive sum equal to 9 function count9s( $number ) { // To store result $count = 0; $n = strlen ( $number ); // Consider every character as // beginning of substring for ( $i = 0; $i < $n ; $i ++) { //sum of digits in // current substring $sum = $number [ $i ] - '0' ; if ( $number [ $i ] == '9' ) $count ++; // One by one choose every character // as an ending character for ( $j = $i + 1; $j < $n ; $j ++) { // 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 $sum = ( $sum + $number [ $j ] - '0' ) % 9; if ( $sum == 0) $count ++; } } return $count ; } // Driver Code echo count9s( "4189" ), "
" ; echo count9s( "1809" ); // This code is contributed by ajit ?> |
Output:
3 5
Time complexity of the above program is O(n2). Please let me know if there is a better solution.
leave a comment
0 Comments