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