Dado un entero representado como una string, necesitamos obtener la suma de todas las substrings posibles de esta string.
Ejemplos:
Input : num = “1234” Output : 1670 Sum = 1 + 2 + 3 + 4 + 12 + 23 + 34 + 123 + 234 + 1234 = 1670 Input : num = “421” Output : 491 Sum = 4 + 2 + 1 + 42 + 21 + 421 = 491
Podemos resolver este problema usando programación dinámica. Podemos escribir una suma de todas las substrings en función del dígito en el que terminan en ese caso,
Suma de todas las substrings = suma de dígitos [0] + suma de dígitos [1] + suma de dígitos [2] … + suma de dígitos [n-1] donde n es la longitud de la string.
Donde sumofdigit[i] almacena la suma de todas las substrings que terminan en i-ésimo dígito índice, en el ejemplo anterior,
Example : num = "1234" sumofdigit[0] = 1 = 1 sumofdigit[1] = 2 + 12 = 14 sumofdigit[2] = 3 + 23 + 123 = 149 sumofdigit[3] = 4 + 34 + 234 + 1234 = 1506 Result = 1670
Ahora podemos obtener la relación entre los valores de suma de dígitos y podemos resolver la pregunta de forma iterativa. Cada suma de dígitos se puede representar en términos del valor anterior como se muestra a continuación,
For above example, sumofdigit[3] = 4 + 34 + 234 + 1234 = 4 + 30 + 4 + 230 + 4 + 1230 + 4 = 4*4 + 10*(3 + 23 +123) = 4*4 + 10*(sumofdigit[2]) In general, sumofdigit[i] = (i+1)*num[i] + 10*sumofdigit[i-1]
Usando la relación anterior podemos resolver el problema en tiempo lineal. En el siguiente código, se toma una array completa para almacenar sumofdigit, ya que cada valor de sumofdigit requiere solo el valor anterior, podemos resolver este problema sin asignar también la array completa.
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; // Utility method to convert character digit to // integer digit int toDigit(char ch) { return (ch - '0'); } // Returns sum of all substring of num int sumOfSubstrings(string num) { int n = num.length(); // allocate memory equal to length of string int sumofdigit[n]; // initialize first value with first digit sumofdigit[0] = toDigit(num[0]); int res = sumofdigit[0]; // loop over all digits of string for (int i = 1; i < n; i++) { int numi = toDigit(num[i]); // update each sumofdigit from previous value sumofdigit[i] = (i + 1) * numi + 10 * sumofdigit[i - 1]; // add current value to the result res += sumofdigit[i]; } return res; } // Driver code to test above methods int main() { string num = "1234"; 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; class GFG { // Returns sum of all substring of num public static int sumOfSubstrings(String num) { int n = num.length(); // allocate memory equal to length of string int sumofdigit[] = new int[n]; // initialize first value with first digit sumofdigit[0] = num.charAt(0) - '0'; int res = sumofdigit[0]; // loop over all digits of string for (int i = 1; i < n; i++) { int numi = num.charAt(i) - '0'; // update each sumofdigit from previous value sumofdigit[i] = (i + 1) * numi + 10 * sumofdigit[i - 1]; // add current value to the result res += sumofdigit[i]; } return res; } // Driver code to test above methods public static void main(String[] args) { String num = "1234"; System.out.println(sumOfSubstrings(num)); } } // This code is contributed by Arnav Kr. Mandal.
Python3
# Python program to print # sum of all substring of # a number represented as # a string # Returns sum of all # substring of num def sumOfSubstrings(num): n = len(num) # allocate memory equal # to length of string sumofdigit = [] # initialize first value # with first digit sumofdigit.append(int(num[0])) res = sumofdigit[0] # loop over all # digits of string for i in range(1, n): numi = int(num[i]) # update each sumofdigit # from previous value sumofdigit.append((i + 1) * numi + 10 * sumofdigit[i - 1]) # add current value # to the result res += sumofdigit[i] return res # Driver code num = "1234" 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; class GFG { // Returns sum of all // substring of num public static int sumOfSubstrings(String num) { int n = num.Length; // allocate memory equal to // length of string int[] sumofdigit = new int[n]; // initialize first value // with first digit sumofdigit[0] = num[0] - '0'; int res = sumofdigit[0]; // loop over all digits // of string for (int i = 1; i < n; i++) { int numi = num[i] - '0'; // update each sumofdigit // from previous value sumofdigit[i] = (i + 1) * numi + 10 * sumofdigit[i - 1]; // add current value // to the result res += sumofdigit[i]; } return res; } // Driver code public static void Main() { String num = "1234"; Console.Write(sumOfSubstrings(num)); } } // This code is contributed by Nitin Mittal.
PHP
<?php // PHP program to print sum of all // substring of a number represented // as a string // Method to convert character // digit to integer digit function toDigit($ch) { return ($ch - '0'); } // Returns sum of all // substring of num function sumOfSubstrings($num) { $n = strlen($num); // allocate memory equal to // length of string $sumofdigit[$n] = 0; // initialize first value // with first digit $sumofdigit[0] = toDigit($num[0]); $res = $sumofdigit[0]; // loop over all digits of string for($i = 1; $i < $n; $i++) { $numi = toDigit($num[$i]); // update each sumofdigit // from previous value $sumofdigit[$i] = ($i + 1) * $numi + 10 * $sumofdigit[$i - 1]; // add current value to the result $res += $sumofdigit[$i]; } return $res; } // Driver Code $num = "1234"; echo sumOfSubstrings($num) ; // This code is contributed by nitin mittal. ?>
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 n = num.length; // allocate memory equal to // length of string let sumofdigit = new Array(n); // initialize first value // with first digit sumofdigit[0] = num[0].charCodeAt() - '0'.charCodeAt(); let res = sumofdigit[0]; // loop over all digits // of string for (let i = 1; i < n; i++) { let numi = num[i].charCodeAt() - '0'.charCodeAt(); // update each sumofdigit // from previous value sumofdigit[i] = (i + 1) * numi + 10 * sumofdigit[i - 1]; // add current value // to the result res += sumofdigit[i]; } return res; } let num = "1234"; document.write(sumOfSubstrings(num)); </script>
1670
Complejidad de tiempo: O(n) donde n es la longitud de la string de entrada.
Espacio Auxiliar: O(n)
O(1) enfoque espacial:
El enfoque es el mismo que el descrito anteriormente. Lo que hemos observado es que en el índice actual dependemos de la suma actual + la suma del índice anterior, por lo que en lugar de almacenar en una array dp, podemos almacenarla en dos variables actual y anterior.
Implementación:
C++14
// C++ program to print sum of all substring of // a number represented as a string #include <bits/stdc++.h> using namespace std; // Utility method to convert character digit to // integer digit int toDigit(char ch) { return (ch - '0'); } // Returns sum of all substring of num int sumOfSubstrings(string num) { int n = num.length(); // storing prev value int prev = toDigit(num[0]); int res = prev; // ans int current = 0; // substrings sum upto current index // loop over all digits of string for (int i = 1; i < n; i++) { int numi = toDigit(num[i]); // update each sumofdigit from previous value current = (i + 1) * numi + 10 * prev; // add current value to the result res += current; prev = current; // update previous } return res; } // Driver code to test above methods int main() { string num = "1234"; 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.*; class GFG{ // Utility method to // convert character // digit to integer digit static int toDigit(char ch) { return (ch - '0'); } // Returns sum of all subString of num static int sumOfSubStrings(String num) { int n = num.length(); // Storing prev value int prev = toDigit(num.charAt(0)); int res = prev; int current = 0; // SubStrings sum upto current index // loop over all digits of String for (int i = 1; i < n; i++) { int numi = toDigit(num.charAt(i)); // Update each sumofdigit // from previous value current = (i + 1) * numi + 10 * prev; // Add current value to the result res += current; // Update previous prev = current; } return res; } // Driver code to test above methods public static void main(String[] args) { String num = "1234"; System.out.print(sumOfSubStrings(num) + "\n"); } } // This code is contributed by gauravrajput1
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) : n = len(num) # storing prev value prev = int(num[0]) res = prev # ans current = 0 # substrings sum upto current index # loop over all digits of string for i in range(1, n) : numi = int(num[i]) # update each sumofdigit from previous value current = (i + 1) * numi + 10 * prev # add current value to the result res += current prev = current # update previous return res num = "1234" print(sumOfSubstrings(num)) # This code is contributed by divyeshrabadiya07
C#
// C# program to print sum of all substring of // a number represented as a string using System; class GFG { // Utility method to // convert character // digit to integer digit static int toDigit(char ch) { return (ch - '0'); } // Returns sum of all subString of num static int sumOfSubStrings(string num) { int n = num.Length; // Storing prev value int prev = toDigit(num[0]); int res = prev; int current = 0; // SubStrings sum upto current index // loop over all digits of String for (int i = 1; i < n; i++) { int numi = toDigit(num[i]); // Update each sumofdigit // from previous value current = (i + 1) * numi + 10 * prev; // Add current value to the result res += current; // Update previous prev = current; } return res; } static void Main() { string num = "1234"; Console.WriteLine(sumOfSubStrings(num)); } } // This code is contributed by divyesh072019
Javascript
<script> // JavaScript program to print // sum of all subString of // a number represented as a String // Utility method to // convert character // digit to integer digit function toDigit(ch) { return (ch - '0'); } // Returns sum of all subString of num function sumOfSubStrings(num) { let n = num.length; // Storing prev value let prev = toDigit(num[0]); let res = prev; let current = 0; // SubStrings sum upto current index // loop over all digits of String for (let i = 1; i < n; i++) { let numi = toDigit(num[i]); // Update each sumofdigit // from previous value current = (i + 1) * numi + 10 * prev; // Add current value to the result res += current; // Update previous prev = current; } return res; } // Driver Code let num = "1234"; document.write(sumOfSubStrings(num) + "\n"); </script>
1670
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Este artículo es una contribución de Utkarsh Trivedi. 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