Number of substrings which recursively add up to 9
The problem is to find the total number of substrings in a given numeric string that recursively add up to 9. We are given a numeric string, and we need to count all the possible substrings such that their individual digits add up to 9. The substrings can be of any length, and they do not need to be consecutive. We can consider single digits as substrings as well if they are equal to 9.
Problem Statement with Example
Let's understand the problem with the given example and how the count is derived step by step:
Given numeric string: "35192169"
num = 35192169
// ----------------
9 --> ➀ 9
2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
216 --> ➄ [2+1+6] = 9
9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
9 --> ➈ 9
3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
351 --> ⑪ [3+5+1] = 9
// --------------
Result = 11
-
Substring "9": The individual digit "9" is equal to 9. So, we count it as one valid substring. Count = 1.
-
Substring "2169": The digits in this substring add up to 9 (2 + 1 + 6 + 9 = 18, and 1 + 8 = 9). Count = 2.
-
Substring "92169": The digits in this substring add up to 9 (9 + 2 + 1 + 6 + 9 = 27, and 2 + 7 = 9). Count = 3.
-
Substring "35192169": The digits in this substring add up to 9 (3 + 5 + 1 + 9 + 2 + 1 + 6 + 9 = 36, and 3 + 6 = 9). Count = 4.
-
Substring "216": The digits in this substring add up to 9 (2 + 1 + 6 = 9). Count = 5.
-
Substring "9216": The digits in this substring add up to 9 (9 + 2 + 1 + 6 = 18, and 1 + 8 = 9). Count = 6.
-
Substring "3519216": The digits in this substring add up to 9 (3 + 5 + 1 + 9 + 2 + 1 + 6 = 27, and 2 + 7 = 9). Count = 7.
-
Substring "51921": The digits in this substring add up to 9 (5 + 1 + 9 + 2 + 1 = 18, and 1 + 8 = 9). Count = 8.
-
Substring "9": Another occurrence of a single digit "9" as a valid substring. Count = 9.
-
Substring "3519": The digits in this substring add up to 9 (3 + 5 + 1 + 9 = 18, and 1 + 8 = 9). Count = 10.
-
Substring "351": The digits in this substring add up to 9 (3 + 5 + 1 = 9). Count = 11.
Pseudocode and Algorithm
To solve this problem, we can use a recursive approach. The recursive function will iterate through the string and check for valid substrings that add up to 9.
Pseudocode:
count = 0
function find9Sum(num, sum, index, n):
if sum != 0 and (sum % 9) == 0:
count += 1
if index < 0:
return
find9Sum(num, sum + (num.charAt(index) - '0'), index - 1, n)
if index == 0 and n > 1:
find9Sum(num, 0, n - 1, n - 1)
n = length(num)
count = 0
find9Sum(num, 0, n - 1, n - 1)
print "Given num : " + num
print "Total Result : " + count
procedure main():
num = "35192169"
task = new SubString()
task.count9SumSubstring(num)
main()
Explanation of the Algorithm
-
We initialize a variable
count
to 0 to keep track of the number of substrings that add up to 9. -
The
find9Sum
function takes four parameters:num
(the numeric string),sum
(the sum of digits in the current substring),index
(the current index being considered), andn
(the total length of the string). -
Within the
find9Sum
function:- If the
sum
is not zero and the sum modulo 9 is zero, we increment thecount
as we have found a valid substring. - If the
index
is less than 0, we have considered all possible substrings for the current recursion path, so we return. - Otherwise, we recursively call the
find9Sum
function with updated parameters:- Increment the
sum
with the digit at the current index (num[index] - '0'
) to consider the current digit in the sum. - Decrement the
index
to consider the next digit in the substring. - If we have reached the first digit (index == 0) and
n
(length of the original string) is greater than 1, we make a recursive call with the index asn - 1
to start a new recursion path.
- Increment the
- If the
-
The
count9SumSubstring
function takes the numeric stringnum
as input and initializes thecount
to 0. It then calls thefind9Sum
function with the initial parameters to start the recursive process. -
Finally, after the recursion is completed, it prints the original string and the final
count
of valid substrings.
Program Solution
/*
Java program for
Number of substrings which recursively add up to 9
*/
public class SubString
{
public int count;
public SubString()
{
this.count = 0;
}
public void find9Sum(String num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
find9Sum(num, sum + (num.charAt(index) - '0'), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
find9Sum(num, 0, n - 1, n - 1);
}
}
public void count9SumSubstring(String num)
{
int n = num.length();
this.count = 0;
find9Sum(num, 0, n - 1, n - 1);
// Display given number
System.out.println(" Given num : " + num);
// Display calculated result
System.out.println(" Total Result : " + this.count);
}
public static void main(String[] args)
{
SubString task = new SubString();
String num = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
}
Output
Given num : 35192169
Total Result : 11
// Include header file
#include <iostream>
#include <string>
using namespace std;
/*
C++ program for
Number of substrings which recursively add up to 9
*/
class SubString
{
public: int count;
SubString()
{
this->count = 0;
}
void find9Sum(string num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this->count++;
}
if (index < 0)
{
return;
}
this->find9Sum(num, sum + (num[index] - '0'), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this->find9Sum(num, 0, n - 1, n - 1);
}
}
void count9SumSubstring(string num)
{
int n = num.length();
this->count = 0;
this->find9Sum(num, 0, n - 1, n - 1);
// Display given number
cout << " Given num : " << num << endl;
// Display calculated result
cout << " Total Result : " << this->count << endl;
}
};
int main()
{
SubString *task = new SubString();
string num = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task->count9SumSubstring(num);
return 0;
}
Output
Given num : 35192169
Total Result : 11
// Include namespace system
using System;
/*
Csharp program for
Number of substrings which recursively add up to 9
*/
public class SubString
{
public int count;
public SubString()
{
this.count = 0;
}
public void find9Sum(String num, int sum, int index, int n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum + (num[index] - '0'), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
public void count9SumSubstring(String num)
{
int n = num.Length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
Console.WriteLine(" Given num : " + num);
// Display calculated result
Console.WriteLine(" Total Result : " + this.count);
}
public static void Main(String[] args)
{
SubString task = new SubString();
String num = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
}
Output
Given num : 35192169
Total Result : 11
package main
import "fmt"
/*
Go program for
Number of substrings which recursively add up to 9
*/
func find9Sum(num string,count *int, sum int, index int, n int) {
if sum != 0 && (sum % 9) == 0 {
*count+=1
}
if index < 0 {
return
}
find9Sum(num,
count,
sum + (int(num[index]) - 48),
index - 1, n)
if index == 0 && n > 1 {
// Recursively find other substring which sum up to 9
find9Sum(num,count, 0, n - 1, n - 1)
}
}
func count9SumSubstring(num string) {
var n int = len(num)
var count int = 0
find9Sum(num,&count, 0, n - 1, n - 1)
// Display given number
fmt.Println(" Given num : ", num)
// Display calculated result
fmt.Println(" Total Result : ", count)
}
func main() {
var num string = "35192169"
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
count9SumSubstring(num)
}
Output
Given num : 35192169
Total Result : 11
<?php
/*
Php program for
Number of substrings which recursively add up to 9
*/
class SubString
{
public $count;
public function __construct()
{
$this->count = 0;
}
public function find9Sum($num, $sum, $index, $n)
{
if ($sum != 0 && ($sum % 9) == 0)
{
$this->count++;
}
if ($index < 0)
{
return;
}
$this->find9Sum($num, $sum +
(ord($num[$index]) -
ord('0')), $index - 1, $n);
if ($index == 0 && $n > 1)
{
// Recursively find other substring which sum up to 9
$this->find9Sum($num, 0, $n - 1, $n - 1);
}
}
public function count9SumSubstring($num)
{
$n = strlen($num);
$this->count = 0;
$this->find9Sum($num, 0, $n - 1, $n - 1);
// Display given number
echo(" Given num : ".$num."\n");
// Display calculated result
echo(" Total Result : ".$this->count."\n");
}
}
function main()
{
$task = new SubString();
$num = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
$task->count9SumSubstring($num);
}
main();
Output
Given num : 35192169
Total Result : 11
/*
Node JS program for
Number of substrings which recursively add up to 9
*/
class SubString
{
constructor()
{
this.count = 0;
}
find9Sum(num, sum, index, n)
{
if (sum != 0 && (sum % 9) == 0)
{
this.count++;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum +
(num.charCodeAt(index) -
'0'.charCodeAt(0)), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
count9SumSubstring(num)
{
var n = num.length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
console.log(" Given num : " + num);
// Display calculated result
console.log(" Total Result : " + this.count);
}
}
function main()
{
var task = new SubString();
var num = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
main();
Output
Given num : 35192169
Total Result : 11
# Python 3 program for
# Number of substrings which recursively add up to 9
class SubString :
def __init__(self) :
self.count = 0
def find9Sum(self, num, sum, index, n) :
if (sum != 0 and(sum % 9) == 0) :
self.count += 1
if (index < 0) :
return
self.find9Sum(num, sum +
(ord(num[index]) - ord('0')), index - 1, n)
if (index == 0 and n > 1) :
# Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1)
def count9SumSubstring(self, num) :
n = len(num)
self.count = 0
self.find9Sum(num, 0, n - 1, n - 1)
# Display given number
print(" Given num : ", num)
# Display calculated result
print(" Total Result : ", self.count)
def main() :
task = SubString()
num = "35192169"
# num = 35192169
# ----------------
# 9 --> ➀ 9
# 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
# 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
# 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
# 216 --> ➄ [2+1+6] = 9
# 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
# 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
# 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
# 9 --> ➈ 9
# 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
# 351 --> ⑪ [3+5+1] = 9
# --------------
# Result = 11
task.count9SumSubstring(num)
if __name__ == "__main__": main()
Output
Given num : 35192169
Total Result : 11
# Ruby program for
# Number of substrings which recursively add up to 9
class SubString
# Define the accessor and reader of class SubString
attr_reader :count
attr_accessor :count
def initialize()
self.count = 0
end
def find9Sum(num, sum, index, n)
if (sum != 0 && (sum % 9) == 0)
self.count += 1
end
if (index < 0)
return
end
self.find9Sum(num, sum + (num[index].ord - '0'.ord), index - 1, n)
if (index == 0 && n > 1)
# Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1)
end
end
def count9SumSubstring(num)
n = num.length
self.count = 0
self.find9Sum(num, 0, n - 1, n - 1)
# Display given number
print(" Given num : ", num, "\n")
# Display calculated result
print(" Total Result : ", self.count, "\n")
end
end
def main()
task = SubString.new()
num = "35192169"
# num = 35192169
# ----------------
# 9 --> ➀ 9
# 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
# 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
# 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
# 216 --> ➄ [2+1+6] = 9
# 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
# 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
# 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
# 9 --> ➈ 9
# 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
# 351 --> ⑪ [3+5+1] = 9
# --------------
# Result = 11
task.count9SumSubstring(num)
end
main()
Output
Given num : 35192169
Total Result : 11
/*
Scala program for
Number of substrings which recursively add up to 9
*/
class SubString(var count: Int)
{
def this()
{
this(0);
}
def find9Sum(
num: String,
sum: Int,
index: Int,
n: Int): Unit = {
if (sum != 0 && (sum % 9) == 0)
{
this.count += 1;
}
if (index < 0)
{
return;
}
find9Sum(num, sum +
(num.charAt(index).toInt - '0'.toInt), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
find9Sum(num, 0, n - 1, n - 1);
}
}
def count9SumSubstring(num: String): Unit = {
var n: Int = num.length();
this.count = 0;
find9Sum(num, 0, n - 1, n - 1);
// Display given number
println(" Given num : " + num);
// Display calculated result
println(" Total Result : " + this.count);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubString = new SubString();
var num: String = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
}
Output
Given num : 35192169
Total Result : 11
import Foundation;
/*
Swift 4 program for
Number of substrings which recursively add up to 9
*/
class SubString
{
var count: Int;
init()
{
self.count = 0;
}
func find9Sum(_ num: [Character],
_ sum: Int,
_ index: Int,
_ n: Int)
{
if (sum != 0 && (sum % 9) == 0)
{
self.count += 1;
}
if (index < 0)
{
return;
}
self.find9Sum(num, sum +
(Int(UnicodeScalar(String(num[index]))!.value) -
Int(UnicodeScalar(String("0"))!.value)), index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
self.find9Sum(num, 0, n - 1, n - 1);
}
}
func count9SumSubstring(_ num: String)
{
let n: Int = num.count;
self.count = 0;
self.find9Sum(Array(num), 0, n - 1, n - 1);
// Display given number
print(" Given num : ", num);
// Display calculated result
print(" Total Result : ", self.count);
}
}
func main()
{
let task: SubString = SubString();
let num: String = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
main();
Output
Given num : 35192169
Total Result : 11
/*
Kotlin program for
Number of substrings which recursively add up to 9
*/
class SubString
{
var count: Int;
constructor()
{
this.count = 0;
}
fun find9Sum(num: String, sum: Int, index: Int, n: Int): Unit
{
if (sum != 0 && (sum % 9) == 0)
{
this.count += 1;
}
if (index < 0)
{
return;
}
this.find9Sum(num, sum +
(num.get(index).toInt() - '0'.toInt()),
index - 1, n);
if (index == 0 && n > 1)
{
// Recursively find other substring which sum up to 9
this.find9Sum(num, 0, n - 1, n - 1);
}
}
fun count9SumSubstring(num: String): Unit
{
val n: Int = num.length;
this.count = 0;
this.find9Sum(num, 0, n - 1, n - 1);
// Display given number
println(" Given num : " + num);
// Display calculated result
println(" Total Result : " + this.count);
}
}
fun main(args: Array < String > ): Unit
{
val task: SubString = SubString();
val num: String = "35192169";
// num = 35192169
// ----------------
// 9 --> ➀ 9
// 2169 --> ➁ [2+1+6+9] => [18] => [1+9] = 9
// 92169 --> ➂ [9+2+1+6+9] => [27] => [2+7] = 9
// 35192169 --> ➃ [3+5+1+9+2+1+6+9] => [36] => [3+6] = 9
// 216 --> ➄ [2+1+6] = 9
// 9216 --> ➅ [9+2+1+6] => [18] => [1+8] = 9
// 3519216 --> ➆ [3+5+1+9+2+1+6] => [27] => [2+7] = 9
// 51921 --> ➇ [5+1+9+2+1] => [18] => [1+8] = 9
// 9 --> ➈ 9
// 3519 --> ➉ [3+5+1+9] => [18] => [1+8] = 9
// 351 --> ⑪ [3+5+1] = 9
// --------------
// Result = 11
task.count9SumSubstring(num);
}
Output
Given num : 35192169
Total Result : 11
Resultant Output Explanation
In the given example, we used the input string "35192169". The algorithm processed the string as described above, and after completion, it printed the original string and the total result, which is 11. This indicates that there are 11 substrings in the given numeric string that recursively add up to 9.
Time Complexity
The time complexity of the provided algorithm is O(2^n), where n is the length of the input numeric string. This is because the recursive function explores all possible combinations of substrings. For each digit, it has two choices: either include it in the current substring or start a new substring. As a result, the number of recursive calls grows exponentially with the length of the string. This makes the algorithm inefficient for large input strings. To optimize the solution further, we can use dynamic programming or memoization to avoid redundant calculations and reduce the time complexity.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment