给定一个数字作为字符串，找到连续递归加起来为9的连续子序列数

2021年4月3日17:38:54 发表评论 931 次浏览

本文概述

C ++
Java
Python 3
C#
的PHP

给定一个数字作为字符串, 编写一个函数来查找给定字符串的子字符串(或连续子序列)的数量, 这些子字符串的递归加起来为9。

例如, 将729的数字递归加到9,

7 + 2 + 9 = 18

18递归

1 + 8 = 9

例子：

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

仅当数字为9的倍数时, 数字的所有数字才会累加9, 我们基本上需要检查所有子字符串s的s％9。下面程序中使用的一个技巧是进行模块化算术, 以避免大字符串溢出。

以下是基于此方法的简单实现。该实现假定输入数字中没有前导0。

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" ), "\n" ;
     echo count9s( "1809" );
      
// This code is contributed by ajit
?>

输出如下：