Calculate sum of all numbers present in a string using recursion
The idea is to recursively traverse over the string and find out the numbers then add these numbers to the result, at last return the result.
Follow the below steps to implement the idea:
- Create an empty string temp and an integer sum.
- Recursively traverse the characters for every index i from 0 to length – 1.
- If i = N-1 then check if current character is a digit return str[i] – ‘0’.
- Else return 0.
- If str[i] is a digit.
- Run a for loop with counter j from i to N – 1.
- If the character is a numeric digit add it to temp.
- Else break.
- Return sum of numeric value of temp + recur for index j.
- Run a for loop with counter j from i to N – 1.
Below is the implementation of the above approach:
C++
// C++ program to calculate sum of all numbers // present in a string containing alphanumeric // characters #include <iostream> using namespace std; int solve(string& str, int i, int n) { // if string is empty if (i >= n) return 0; // if on the last index if (i == n - 1) { // if last digit is numeric if ( isdigit (str[i])) { return str[i] - '0' ; } else { return 0; } } // if current char is digit // then sum the consecutive digits if ( isdigit (str[i])) { // declared an empty string string temp = "" ; int j; // start from that index // sum all the consecutive digits for (j = i; j < n; j++) { // if current char is digit // add it to the temp string if ( isdigit (str[j])) temp += str[j]; // if it is not a digit // break instantly else break ; } // add the number associated to temp // with the answer recursion will bring return stoi(temp) + solve(str, j, n); } // else call from the next index else { solve(str, i + 1, n); } } int findSum(string str) { // recursiven function return solve(str, 0, str.size()); } // Driver code int main() { // input alphanumeric string string str = "12abc20yz68" ; // Function call cout << findSum(str); return 0; } |
Java
import java.util.Scanner; class Main { static int solve(String str, int i, int n) { // if string is empty if (i >= n) return 0 ; // if on the last index if (i == n - 1 ) { // if last digit is numeric if (Character.isDigit(str.charAt(i))) { return str.charAt(i) - '0' ; } else { return 0 ; } } // if current char is digit // then sum the consecutive digits if (Character.isDigit(str.charAt(i))) { // declared an empty string String temp = "" ; int j; // start from that index // sum all the consecutive digits for (j = i; j < n; j++) { // if current char is digit // add it to the temp string if (Character.isDigit(str.charAt(j))) temp += str.charAt(j); // if it is not a digit // break instantly else break ; } // add the number associated to temp // with the answer recursion will bring return Integer.parseInt(temp) + solve(str, j, n); } // else call from the next index else { return solve(str, i + 1 , n); } } static int findSum(String str) { // recursiven function return solve(str, 0 , str.length()); } // Driver code public static void main(String[] args) { // input alphanumeric string String str = "12abc20yz68" ; // Function call System.out.println(findSum(str)); } } // This code contributed by Ajax |
Python3
def findSum( str ): # variable to store sum result = 0 temp = "" for i in range ( len ( str )): if str [i].isnumeric(): temp + = str [i] if i = = len ( str ) - 1 : result + = int (temp) else : if temp ! = "": result + = int (temp) temp = "" return result # driver code if __name__ = = "__main__" : # input alphanumeric string str = "12abc20yz68" print (findSum( str )) #This code contributed by Shivam Tiwari |
C#
// C# program to calculate sum of all numbers // present in a string containing alphanumeric // characters using System; using System.Linq; using System.Collections.Generic; class GFG { static bool isdigit( char c) { if (c>= '0' && c<= '9' ) return true ; return false ; } static int solve( string str, int i, int n) { // if string is empty if (i >= n) return 0; // if on the last index if (i == n - 1) { // if last digit is numeric if (isdigit(str[i])) { return str[i]; } else { return 0; } } // if current char is digit // then sum the consecutive digits if (isdigit(str[i])) { // declared an empty string string temp = "" ; int j; // start from that index // sum all the consecutive digits for (j = i; j < n; j++) { // if current char is digit // add it to the temp string if (isdigit(str[j])) temp += str[j]; // if it is not a digit // break instantly else break ; } // add the number associated to temp // with the answer recursion will bring return Int32.Parse(temp) + solve(str, j, n); } // else call from the next index else { return solve(str, i + 1, n); } } static int findSum( string str) { // recursiven function return solve(str, 0, str.Length); } // Driver code static public void Main() { // input alphanumeric string string str = "12abc20yz68" ; // Function call Console.Write(findSum(str)); } } |
Javascript
function findSum(str) { // variable to store sum let result = 0; let temp = "" ; for (let i = 0; i < str.length; i++) { if (!isNaN(str[i])) { temp += str[i]; if (i === str.length - 1) { result += parseInt(temp); } } else { if (temp !== "" ) { result += parseInt(temp); temp = "" ; } } } return result; } // driver code console.log(findSum( "12abc20yz68" )); // This code is contributed by Shivam Tiwari |
Output
100
Time Complexity: O(N), where N is the size of the given string.
Auxiliary Space: O(N), in worst case it can cost O(N) recursive calls
Calculate sum of all numbers present in a string
Given a string S containing alphanumeric characters, The task is to calculate the sum of all numbers present in the string.
Examples:
Input: 1abc23
Output: 24
Explanation: 1 + 23 = 24Input: geeks4geeks
Output: 4Input: 1abc2x30yz67
Output: 100