Given a number as a string, find the number of contiguous subsequences which recursively add up to 9

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 #include 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; }

/div>

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



Output:

3
5

Time complexity of the above program is O(n2). Please let me know if there is a better solution.

Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 | Set 2

tags:

Strings subsequence Strings