本文概述
- C ++
- Java
- Python 3
- C#
- 的PHP
例如, 将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
本文作者:阿比舍克。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- C++中的抽象编程详细指南和介绍
- 2017最新win10专业版一键安装系统安装图文详细教程
- win10官方升级工具安装图文详细教程
- 2017win10秋季正式版版公布时间及新特点最新推荐
- 本图文详细教程教你如何让你的win10系统更新升级
- 本图文详细教程教你win10开始菜单打开不了时该怎样办
- 本图文详细教程教你U盘Win7 升级Win10系统办法
- 2017年windows10永久激活密钥大全最新推荐
- windows10激活密匙分享制作详细说明