Open In App

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

Improve
Improve
Like Article
Like
Save
Share
Report

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.

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(string number)
{
    int count = 0; // To store result
    int n = number.size();
 
    // 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"),"\n";
    echo count9s("1809");
     
// This code is contributed by ajit
?>


Javascript




<script>
 
// JavaScript program to count substrings
// with recursive sum equal to 9
 
  function count9s(number){
      // To store result
      let count = 0;
      let n = (number.length);
      // Consider every character as beginning of substring
      for (let i = 0; i < n; i++)
      {
          //sum of digits in current substring
          let sum = number[i] - '0'
 
          if (number[i] == '9'){ count++;}
 
          // One by one choose every character
          // as an ending character
          for (let 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
   
  document.write( count9s("4189") );
  document.write("</br>");
  document.write( count9s("1809"));
   
</script>


Output

3
5

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

Auxiliary Space :O(1), since no extra space is used.
Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 | Set 2 



Last Updated : 31 Jan, 2023
Like Article
Save Article
Previous
Next
Share your thoughts in the comments
Similar Reads