Dada una string que representa un número, necesitamos obtener la suma de todas las substrings posibles de esta string.
Ejemplos:
Input : s = "6759"
Output : 8421
sum = 6 + 7 + 5 + 9 + 67 + 75 +
59 + 675 + 759 + 6759
= 8421
Input : s = "16"
Output : 23
sum = 1 + 6 + 16 = 23
Hemos discutido una solución en la publicación a continuación.
Suma de todas las substrings de una string que representa un número | Serie 1
La solución se basa en un enfoque diferente que no utiliza espacio adicional.
Este problema se puede ver de la siguiente manera.
Sea el número s = “6759”
1 10 100 1000
6 1 1 1 1
7 2 2 2
5 3 3
9 4
La tabla anterior indica que, cuando todas las substrings se convierten en unidades, decenas, centenas, etc., cada índice de la string tendrá una ocurrencia fija. El 1.er índice tendrá 1 ocurrencia de unidades, decenas, etc. El 2.º tendrá 2, el 3.º tendrá 3 y así sucesivamente.
Un punto más es que la ocurrencia del último elemento solo estará restringida a unos. El último segundo elemento estará restringido a unidades y decenas. el último tercero será hasta cien y así sucesivamente.
A partir de los puntos anteriores vamos a averiguar la suma.
sum = 6*(1*1 + 1*10 + 1*100 + 1*1000) + 7*(2*1 + 2*10 + 2*100) +
5*(3*1 + 3*10) + 9*(4*1)
= 6*1*(1111) + 7*2*(111) + 5*3*(11) + 9*4*(1)
= 6666 + 1554 + 165 + 36
= 8421
Ahora, para manejar la multiplicación, tendremos un factor multiplicador que comienza desde 1. Está claro en el ejemplo que el factor multiplicador (al revés) es 1, 11, 111, … y así sucesivamente. Entonces la multiplicación se basará en tres factores. número, su índice y un factor multiplicador.
Implementación:
C++
// C++ program to print sum of all substring of
// a number represented as a string
#include <bits/stdc++.h>
using namespace std;
// Returns sum of all substring of num
int sumOfSubstrings(string num)
{
long long int sum = 0; // Initialize result
// Here traversing the array in reverse
// order.Initializing loop from last
// element.
// mf is multiplying factor.
long long int mf = 1;
for (int i=num.size()-1; i>=0; i--)
{
// Each time sum is added to its previous
// sum. Multiplying the three factors as
// explained above.
// s[i]-'0' is done to convert char to int.
sum += (num[i]-'0')*(i+1)*mf;
// Making new multiplying factor as
// explained above.
mf = mf*10 + 1;
}
return sum;
}
// Driver code to test above methods
int main()
{
string num = "6759";
cout << sumOfSubstrings(num) << endl;
return 0;
}
Java
// Java program to print sum of all substring of
// a number represented as a string
import java.util.Arrays;
public class GFG {
// Returns sum of all substring of num
public static long sumOfSubstrings(String num)
{
long sum = 0; // Initialize result
// Here traversing the array in reverse
// order.Initializing loop from last
// element.
// mf is multiplying factor.
long mf = 1;
for (int i = num.length() - 1; i >= 0; i --)
{
// Each time sum is added to its previous
// sum. Multiplying the three factors as
// explained above.
// s[i]-'0' is done to convert char to int.
sum += (num.charAt(i) - '0') * (i + 1) * mf;
// Making new multiplying factor as
// explained above.
mf = mf * 10 + 1;
}
return sum;
}
// Driver code to test above methods
public static void main(String[] args)
{
String num = "6759";
System.out.println(sumOfSubstrings(num));
}
}
// This code is contributed by Arnav Kr. Mandal.
Python3
# Python3 program to print sum of all substring of # a number represented as a string # Returns sum of all substring of num def sumOfSubstrings(num): sum = 0 # Initialize result # Here traversing the array in reverse # order.Initializing loop from last # element. # mf is multiplying factor. mf = 1 for i in range(len(num) - 1, -1, -1): # Each time sum is added to its previous # sum. Multiplying the three factors as # explained above. # int(s[i]) is done to convert char to int. sum = sum + (int(num[i])) * (i + 1) * mf # Making new multiplying factor as # explained above. mf = mf * 10 + 1 return sum # Driver code to test above methods if __name__=='__main__': num = "6759" print(sumOfSubstrings(num)) # This code is contributed by # Sanjit_Prasad
C#
// C# program to print sum of all substring of
// a number represented as a string
using System;
public class GFG {
// Returns sum of all substring of num
public static long sumOfSubstrings(string num)
{
long sum = 0; // Initialize result
// Here traversing the array in reverse
// order.Initializing loop from last
// element.
// mf is multiplying factor.
long mf = 1;
for (int i = num.Length - 1; i >= 0; i --)
{
// Each time sum is added to its previous
// sum. Multiplying the three factors as
// explained above.
// s[i]-'0' is done to convert char to int.
sum += (num[i] - '0') * (i + 1) * mf;
// Making new multiplying factor as
// explained above.
mf = mf * 10 + 1;
}
return sum;
}
// Driver code to test above methods
public static void Main()
{
string num = "6759";
Console.WriteLine(sumOfSubstrings(num));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to print sum of
// all substring of a number
// represented as a string
// Returns sum of all
// substring of num
function sumOfSubstrings($num)
{
// Initialize result
$sum = 0;
// Here traversing the array
// in reverse order.Initializing
// loop from last element.
// mf is multiplying factor.
$mf = 1;
for ($i = strlen($num) - 1; $i >= 0; $i--)
{
// Each time sum is added to
// its previous sum. Multiplying
// the three factors as explained above.
// s[i]-'0' is done to convert char to int.
$sum += ($num[$i] - '0') * ($i + 1) * $mf;
// Making new multiplying
// factor as explained above.
$mf = $mf * 10 + 1;
}
return $sum;
}
// Driver Code
$num = "6759";
echo sumOfSubstrings($num), "\n";
// This code is contributed by m_kit
?>
Javascript
<script>
// Javascript program to print sum of all substring of
// a number represented as a string
// Returns sum of all substring of num
function sumOfSubstrings(num)
{
let sum = 0; // Initialize result
// Here traversing the array in reverse
// order.Initializing loop from last
// element.
// mf is multiplying factor.
let mf = 1;
for (let i = num.length - 1; i >= 0; i --)
{
// Each time sum is added to its previous
// sum. Multiplying the three factors as
// explained above.
// s[i]-'0' is done to convert char to int.
sum += (num[i].charCodeAt() - '0'.charCodeAt()) * (i + 1) * mf;
// Making new multiplying factor as
// explained above.
mf = mf * 10 + 1;
}
return sum;
}
let num = "6759";
document.write(sumOfSubstrings(num));
// This code is contributed by rameshtravel07.
</script>
8421
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Jatin Goyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA