Dada la string str que tiene N caracteres que representan un número entero, la tarea es calcular la suma de todos los prefijos posibles de la string dada.
Ejemplo:
Entrada: str = “1225”
Salida: 1360
Explicación: Los prefijos de la string dada son 1, 12, 122 y 1225 y su suma será 1 + 12 + 122 + 1225 = 1360.Entrada: str = «20»
Salida: 22
Enfoque: el problema dado es un problema basado en la implementación y se puede resolver iterando sobre todos los prefijos de la string y manteniendo su suma en una string. La suma de dos números enteros representados como strings se puede hacer usando el enfoque discutido aquí .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function for finding sum of larger numbers
string 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 number
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 += str[i];
// Update Sum
sum = findSum(curPre, sum);
}
// Return Answer
return sum;
}
// Driver Code
int main()
{
string str = "1225";
cout << sumPrefix(str);
return 0;
}
Java
// Java program of the above approach
import java.util.*;
class GFG{
// Function for finding sum of larger numbers
static 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 number
static 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 Code
public 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 numbers
def 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 number
def 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 Code
str = "1225";
print(sumPrefix(str));
# This code is contributed by Saurabh Jaiswal
C#
// C# program of the above approach
using System;
public class GFG{
// Function for finding sum of larger numbers
static 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 number
static 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 Code
public 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>
Producción
1360
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por arunbang17 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA