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: 909 Output: 5 There are 5 substrings which recursively add to nine, 9, 90, 909, 09, 9
This article is about an optimized solution of problem stated below article :
Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 | Set 1.
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.
Algorithm:
Initialize an array d of size 10 with 0
d[0]<-1
Initialize mod_sum = 0, continuous_zero = 0
for every character
if character == '0';
continuous_zero++
else
continuous_zero=0
compute mod_sum
update result += d[mod_sum]
update d[mod_sum]++
subtract those cases from result which have only 0s
Explanation:
If sum of digits from index i to j add up to 9, then sum(0 to i-1) = sum(0 to j) (mod 9).
We just have to remove cases which contain only zeroes.We can do this by remembering the no. of continuous zeroes upto this character(no. of these cases ending on this index) and subtracting them from the result.
Following is a simple implementation based on this approach.
The implementation assumes that there are can be leading 0’s in the 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 n = strlen(number); // to store no. of previous encountered modular sums int d[9]; memset(d, 0, sizeof(d)); // no. of modular sum(==0) encountered till now = 1 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')) // if number is 0 increase continuous_zero++; // no. of continuous_zero by 1 else // else continuous_zero is 0 continuous_zero=0; mod_sum += int(number[i] - '0'); mod_sum %= 9; result+=d[mod_sum]; d[mod_sum]++; // increase d value of this mod_sum // subtract no. of cases where there // are only zeroes in substring result -= continuous_zero; } return result;}// driver program to test above functionint main(){ cout << count9s("01809") << endl; cout << count9s("1809") << endl; cout << count9s("4189"); return 0;}// This code is contributed by Gulab Arora |
Java
// Java program to count substrings with recursive sum equal to 9class GFG { static int count9s(char number[]) { int n = number.length; // to store no. of previous encountered modular sums int d[] = new int[9]; // no. of modular sum(==0) encountered till now = 1 d[0] = 1; int result = 0; int mod_sum = 0, continuous_zero = 0; for (int i = 0; i < n; i++) { if ((number[i] - '0') == 0) // if number is 0 increase { continuous_zero++; // no. of continuous_zero by 1 } else // else continuous_zero is 0 { continuous_zero = 0; } mod_sum += (number[i] - '0'); mod_sum %= 9; result += d[mod_sum]; d[mod_sum]++; // increase d value of this mod_sum // subtract no. of cases where there // are only zeroes in substring result -= continuous_zero; } return result; }// driver program to test above function public static void main(String[] args) { System.out.println(count9s("01809".toCharArray())); System.out.println(count9s("1809".toCharArray())); System.out.println(count9s("4189".toCharArray())); }}// This code is contributed by 29AjayKumar |
Python3
# Python 3 program to count substrings with # recursive sum equal to 9def count9s(number): n = len(number) # to store no. of previous encountered # modular sums d = [0 for i in range(9)] # no. of modular sum(==0) encountered # till now = 1 d[0] = 1 result = 0 mod_sum = 0 continuous_zero = 0 for i in range(n): # if number is 0 increase if (ord(number[i]) - ord('0') == 0): continuous_zero += 1 # no. of continuous_zero by 1 else: continuous_zero = 0 # else continuous_zero is 0 mod_sum += ord(number[i]) - ord('0') mod_sum %= 9 result += d[mod_sum] d[mod_sum] += 1 # increase d value of this mod_sum # subtract no. of cases where there # are only zeroes in substring result -= continuous_zero return result# Driver Codeif __name__ == '__main__': print(count9s("01809")) print(count9s("1809")) print(count9s("4189")) # This code is contributed by# Sahil_Shelangia |
C#
// C# program to count substrings with recursive sum equal to 9 using System;class GFG { static int count9s(string number) { int n = number.Length; // to store no. of previous encountered modular sums int[] d = new int[9]; // no. of modular sum(==0) encountered till now = 1 d[0] = 1; int result = 0; int mod_sum = 0, continuous_zero = 0; for (int i = 0; i < n; i++) { if ((number[i] - '0') == 0) // if number is 0 increase { continuous_zero++; // no. of continuous_zero by 1 } else // else continuous_zero is 0 { continuous_zero = 0; } mod_sum += (number[i] - '0'); mod_sum %= 9; result += d[mod_sum]; d[mod_sum]++; // increase d value of this mod_sum // subtract no. of cases where there // are only zeroes in substring result -= continuous_zero; } return result; } // driver program to test above function public static void Main() { Console.WriteLine(count9s("01809")); Console.WriteLine(count9s("1809")); Console.WriteLine(count9s("4189")); }} |
Javascript
<script>// Javascript program to count substrings with recursive sum equal to 9 function count9s(number) { let n = number.length; // to store no. of previous encountered modular sums let d = new Array(9); for(let i=0;i<d.length;i++) { d[i]=0; } // no. of modular sum(==0) encountered till now = 1 d[0] = 1; let result = 0; let mod_sum = 0, continuous_zero = 0; for (let i = 0; i < n; i++) { if ((number[i] - '0') == 0) // if number is 0 increase { continuous_zero++; // no. of continuous_zero by 1 } else // else continuous_zero is 0 { continuous_zero = 0; } mod_sum += (number[i] - '0'); mod_sum %= 9; result += d[mod_sum]; d[mod_sum]++; // increase d value of this mod_sum // subtract no. of cases where there // are only zeroes in substring result -= continuous_zero; } return result; } // driver program to test above function document.write(count9s("01809")+"<br>"); document.write(count9s("1809")+"<br>"); document.write(count9s("4189")+"<br>"); //This code is contributed by avanitrachhadiya2155 </script> |
Output:
8 5 3
Time Complexity of the above program is O(n). Program also supports leading zeroes.
Auxiliary Space: O(1).
This article is contributed by Gulab Arora. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
