Given string str having N characters representing an integer, the task is to calculate the sum of all possible prefixes of the given string.
Example:
Input: str = “1225”
Output: 1360
Explanation: The prefixes of the given string are 1, 12, 122, and 1225 and their sum will be 1 + 12 + 122 + 1225 = 1360.Input: str = “20”
Output: 22
Approach: The given problem is an implementation-based problem and can be solved by iterating over all the prefixes of the string and maintaining their sum in a string. The sum of two integers represented as strings can be done using the approach discussed here.
Below is the implementation of the above approach:
C++
// C++ program of the above approach#include <bits/stdc++.h>using namespace std;// Function for finding sum of larger numbersstring findSum(string str1, string str2){ // Before proceeding further, make // sure length of str2 is larger if (str1.length() > str2.length()) swap(str1, str2); // Stores resulting sum string str = ""; // Calculate length of both string int n1 = str1.length(), n2 = str2.length(); // Reverse both of strings reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; for (int i = 0; i < n1; i++) { // Compute sum of current // digits and carry int sum = ((str1[i] - '0') + (str2[i] - '0') + carry); str.push_back(sum % 10 + '0'); // Carry for next step carry = sum / 10; } // Add remaining digits for (int i = n1; i < n2; i++) { int sum = ((str2[i] - '0') + carry); str.push_back(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry) str.push_back(carry + '0'); // Reverse string reverse(str.begin(), str.end()); // Return Answer return str;}// Function to find sum of all prefixes// of a string representing a numberstring sumPrefix(string str){ // Stores the desired sum string sum = "0"; // Stores the current prefix string curPre = ""; // Loop to iterate str for (int i = 0; i < str.length(); i++) { // Update current prefix curPre += str[i]; // Update Sum sum = findSum(curPre, sum); } // Return Answer return sum;}// Driver Codeint main(){ string str = "1225"; cout << sumPrefix(str); return 0;} |
Java
// Java program of the above approachimport java.util.*;class GFG{// Function for finding sum of larger numbersstatic String findSum(String str1, String str2){ // Before proceeding further, make // sure length of str2 is larger if (str1.length() > str2.length()) { String s = str1; str1=str2; str2=s; } // Stores resulting sum String str = ""; // Calculate length of both String int n1 = str1.length(), n2 = str2.length(); // Reverse both of Strings str1 = reverse(str1); str2 = reverse(str2); int carry = 0; for (int i = 0; i < n1; i++) { // Compute sum of current // digits and carry int sum = ((str1.charAt(i) - '0') + (str2.charAt(i) - '0') + carry); str+=(char)((sum % 10 + '0')); // Carry for next step carry = sum / 10; } // Add remaining digits for (int i = n1; i < n2; i++) { int sum = ((str2.charAt(i) - '0') + carry); str+=(char)(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry > 0) str += (carry + '0'); // Reverse String str = reverse(str); // Return Answer return str;}// Function to find sum of all prefixes// of a String representing a numberstatic String sumPrefix(String str){ // Stores the desired sum String sum = "0"; // Stores the current prefix String curPre = ""; // Loop to iterate str for (int i = 0; i < str.length(); i++) { // Update current prefix curPre += (char)(str.charAt(i)); // Update Sum sum = findSum(curPre, sum); } // Return Answer return sum;}static String reverse(String input) { char[] a = input.toCharArray(); int l, r = a.length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.valueOf(a);} // Driver Codepublic static void main(String[] args){ String str = "1225"; System.out.print(sumPrefix(str));}}// This code is contributed by shikhasingrajput |
Python3
# Python code for the above approach # Function for finding sum of larger numbersdef findSum(str1, str2): # Before proceeding further, make # sure length of str2 is larger if (len(str1) > len(str2)): temp = str1; str1 = str2; str2 = temp; # Stores resulting sum str = []; # Calculate length of both string n1 = len(str1) n2 = len(str2) # Reverse both of strings str1 = list(str1) str2 = list(str2) str1.reverse(); str2.reverse(); carry = 0; for i in range(n1): # Compute sum of current # digits and carry sum = ((ord(str1[i]) - ord('0')) + (ord(str2[i]) - ord('0')) + carry); str.append(chr(sum % 10 + ord('0'))); # Carry for next step carry = sum // 10 # Add remaining digits for i in range(n1, n2): sum = ((ord(str2[i]) - ord('0')) + carry); str.append(chr(sum % 10 + ord('0'))); carry = sum // 10 # Add remaining carry if (carry): str.append(chr(carry + ord('0'))); # Reverse string str.reverse(); # Return Answer return ''.join(str)# Function to find sum of all prefixes# of a string representing a numberdef sumPrefix(str): # Stores the desired sum sum = "0"; # Stores the current prefix curPre = ""; # Loop to iterate str for i in range(len(str)): # Update current prefix curPre += str[i]; # Update Sum sum = findSum(curPre, sum); # Return Answer return sum;# Driver Codestr = "1225";print(sumPrefix(str));# This code is contributed by Saurabh Jaiswal |
C#
// C# program of the above approachusing System;public class GFG{// Function for finding sum of larger numbersstatic String findSum(String str1, String str2){ // Before proceeding further, make // sure length of str2 is larger if (str1.Length > str2.Length) { String s = str1; str1=str2; str2=s; } // Stores resulting sum String str = ""; // Calculate length of both String int n1 = str1.Length, n2 = str2.Length; // Reverse both of Strings str1 = reverse(str1); str2 = reverse(str2); int carry = 0; for (int i = 0; i < n1; i++) { // Compute sum of current // digits and carry int sum = ((str1[i] - '0') + (str2[i] - '0') + carry); str+=(char)((sum % 10 + '0')); // Carry for next step carry = sum / 10; } // Add remaining digits for (int i = n1; i < n2; i++) { int sum = ((str2[i] - '0') + carry); str+=(char)(sum % 10 + '0'); carry = sum / 10; } // Add remaining carry if (carry > 0) str += (carry + '0'); // Reverse String str = reverse(str); // Return Answer return str;}// Function to find sum of all prefixes// of a String representing a numberstatic String sumPrefix(String str){ // Stores the desired sum String sum = "0"; // Stores the current prefix String curPre = ""; // Loop to iterate str for (int i = 0; i < str.Length; i++) { // Update current prefix curPre += (char)(str[i]); // Update Sum sum = findSum(curPre, sum); } // Return Answer return sum;}static String reverse(String input) { char[] a = input.ToCharArray(); int l, r = a.Length - 1; for (l = 0; l < r; l++, r--) { char temp = a[l]; a[l] = a[r]; a[r] = temp; } return String.Join("",a);} // Driver Codepublic static void Main(String[] args){ String str = "1225"; Console.Write(sumPrefix(str));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function for finding sum of larger numbers function findSum(str1, str2) { // Before proceeding further, make // sure length of str2 is larger if (str1.length > str2.length) { let temp = str1; str1 = str2; str2 = temp; } // Stores resulting sum let str = []; // Calculate length of both string let n1 = str1.length, n2 = str2.length; // Reverse both of strings str1 = str1.split('') str2 = str2.split('') str1.reverse(); str2.reverse(); let carry = 0; for (let i = 0; i < n1; i++) { // Compute sum of current // digits and carry let sum = ((str1[i].charCodeAt(0) - '0'.charCodeAt(0)) + (str2[i].charCodeAt(0) - '0'.charCodeAt(0)) + carry); str.push(String.fromCharCode(sum % 10 + '0'.charCodeAt(0))); // Carry for next step carry = Math.floor(sum / 10); } // Add remaining digits for (let i = n1; i < n2; i++) { let sum = ((str2[i].charCodeAt(0) - '0'.charCodeAt(0)) + carry); str.push(String.fromCharCode(sum % 10 + '0'.charCodeAt(0))); carry = Math.floor(sum / 10); } // Add remaining carry if (carry) str.push(String.fromCharCode(carry + '0'.charCodeAt(0))); // Reverse string str.reverse(); // Return Answer return str.join(''); } // Function to find sum of all prefixes // of a string representing a number function sumPrefix(str) { // Stores the desired sum let sum = "0"; // Stores the current prefix let curPre = ""; // Loop to iterate str for (let i = 0; i < str.length; i++) { // Update current prefix curPre += str[i]; // Update Sum sum = findSum(curPre, sum); } // Return Answer return sum; } // Driver Code let str = "1225"; document.write(sumPrefix(str)); // This code is contributed by Potta Lokesh </script> |
Output
1360
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
