Suma de todas las substrings de una string que representa un número | Serie 1

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++ 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 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.

# 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# 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 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.
?>

<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)

Suma de todas las substrings de una string que representa un número | Conjunto 2 (espacio adicional constante)

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++ 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 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 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# 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

<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.