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

本文概述

  • 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的倍数时, 数字的所有数字才会累加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 substringif (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 9def 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' )) % 9if ( 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 9function 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 ?>

输出如下:
3 5

上面程序的时间复杂度是O(n2)。请让我知道是否有更好的解决方案。
给定一个数字作为字符串, 找到递归加起来为9 |的连续子序列数。套装2
本文作者:阿比舍克。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

    推荐阅读