Dada la string numérica str que consta de N enteros, la tarea es encontrar la suma de todas las posibles strings resultantes después de eliminar las substrings no vacías .
Ejemplos:
Entrada: str = “205”
Salida: 57
Explicación: Las substrings que se pueden eliminar son “2”, “0”, “5”, “20”, “05”, “205”. Las strings resultantes son «05», «25», «20», «5», «2», «0» respectivamente. Por lo tanto, la suma será 57.Entrada: str = “1234”
Salida: 680
Explicación: Las substrings que se pueden eliminar son “1”, “2”, “3”, “4”, “12”, “23”, “34”, “123”, “234”, “1234”. Las strings resultantes son «234», «134», «124», «123», «34», «14», «12», «4», «1», «0» respectivamente. Por lo tanto, la suma será 680.
Planteamiento: Para resolver el problema, es necesario hacer las siguientes observaciones:
Ilustración:
Sea str = “1234”
Todas las strings posibles mediante la eliminación de substrings no vacías y la posición de cada carácter en estas strings son las siguientes:
100 10 1 234 2 3 4 134 1 3 4 124 1 2 4 123 1 2 3 34 3 4 14 1 4 12 1 2 4 4 1 1 0 0 De la tabla anterior, obtenga la contribución en cada índice, por ejemplo, Contribución en 1 -> ((1 + 2 + 3) * 1 + 4 * 6) * 1
Contribución a los 10 -> ((1 + 2) * 2 + 3 * 3) * 10
Contribución al 100 -> ((1) * 3 + 2 * 1) * 100
Por lo tanto, genere una fórmula general para cada índice, es decir
Contribución a 10 x = (∑(n – x – 2) * (x + 1) + str[n – x – 1] * (n – x – 1)término del número triangular ) * 10 x
Siga los pasos a continuación para resolver el problema:
- Calcule previamente las potencias de 10 y guárdelas en una array power[] .
- Almacene la suma del prefijo de los dígitos de la string numérica dada en la array pref[] .
- Aplicando la fórmula anterior obtenida, para cada x de 0 a N – 1 , calcular la suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int pref[N], power[N];
// Function to convert a character
// to its equivalent digit
int toDigit(char ch)
{
return (ch - '0');
}
// Function to precompute powers of 10
void powerOf10()
{
power[0] = 1;
for (int i = 1; i < N; i++)
power[i] = power[i - 1] * 10;
}
// Function to precompute prefix sum
// of numerical strings
void precomputePrefix(string str, int n)
{
pref[0] = str[0] - '0';
for (int i = 1; i < n; i++)
pref[i] = pref[i - 1]
+ toDigit(str[i]);
}
// Function to return the i-th
// term of Triangular Number
int triangularNumber(int i)
{
int res = i * (i + 1) / 2;
return res;
}
// Function to return the sum
// of all resulting strings
int sumOfSubstrings(string str)
{
int n = str.size();
// Precompute powers of 10
powerOf10();
// Precompute prefix sum
precomputePrefix(str, n);
// Initialize result
int ans = 0;
for (int i = 0; i < n - 1; i++) {
// Apply the above general
// formula for every i
ans += (pref[n - i - 2] * (i + 1)
+ toDigit(str[n - i - 1])
* triangularNumber(
n - i - 1))
* power[i];
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
string str = "1234";
// Function Call
cout << sumOfSubstrings(str);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
static int N = 10;
static int []pref = new int[N];
static int[] power = new int[N];
// Function to convert a
// character to its equivalent
// digit
static int toDigit(char ch)
{
return (ch - '0');
}
// Function to precompute
// powers of 10
static void powerOf10()
{
power[0] = 1;
for (int i = 1; i < N; i++)
power[i] = power[i - 1] * 10;
}
// Function to precompute prefix sum
// of numerical Strings
static void precomputePrefix(char[] str,
int n)
{
pref[0] = str[0] - '0';
for (int i = 1; i < n; i++)
pref[i] = pref[i - 1] +
toDigit(str[i]);
}
// Function to return the i-th
// term of Triangular Number
static int triangularNumber(int i)
{
int res = i * (i + 1) / 2;
return res;
}
// Function to return the sum
// of all resulting Strings
static int sumOfSubStrings(String str)
{
int n = str.length();
// Precompute powers of 10
powerOf10();
// Precompute prefix sum
precomputePrefix(
str.toCharArray(), n);
// Initialize result
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
// Apply the above general
// formula for every i
ans += (pref[n - i - 2] * (i + 1) +
toDigit(str.charAt(n - i - 1)) *
triangularNumber(n - i - 1)) *
power[i];
}
// Return the answer
return ans;
}
// Driver Code
public static void main(String[] args)
{
String str = "1234";
// Function Call
System.out.print(sumOfSubStrings(str));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python 3 program for the
# above approach
N = 10
pref = [0] * N
power = [0] * N
# Function to convert a
# character to its equivalent
# digit
def toDigit(ch):
return (ord(ch) -
ord('0'))
# Function to precompute
# powers of 10
def powerOf10():
power[0] = 1
for i in range(1, N):
power[i] = power[i - 1] * 10
# Function to precompute prefix sum
# of numerical strings
def precomputePrefix(st, n):
pref[0] = (ord(st[0]) -
ord('0'))
for i in range(1, n):
pref[i] = (pref[i - 1] +
toDigit(st[i]))
# Function to return the i-th
# term of Triangular Number
def triangularNumber(i):
res = i * (i + 1) // 2
return res
# Function to return the sum
# of all resulting strings
def sumOfSubstrings(st):
n = len(st)
# Precompute powers
# of 10
powerOf10()
# Precompute prefix
# sum
precomputePrefix(st, n)
# Initialize result
ans = 0
for i in range(n - 1):
# Apply the above general
# formula for every i
ans += ((pref[n - i - 2] * (i + 1) +
toDigit(st[n - i - 1]) *
triangularNumber(n - i - 1)) *
power[i])
# Return the answer
return ans
# Driver Code
if __name__ == "__main__":
st = "1234"
# Function Call
print(sumOfSubstrings(st))
# This code is contributed by Chitranayal
C#
// C# program for the
// above approach
using System;
class GFG{
static int N = 10;
static int []pref = new int[N];
static int[] power = new int[N];
// Function to convert a
// character to its equivalent
// digit
static int toDigit(char ch)
{
return (ch - '0');
}
// Function to precompute
// powers of 10
static void powerOf10()
{
power[0] = 1;
for (int i = 1; i < N; i++)
power[i] = power[i - 1] * 10;
}
// Function to precompute prefix sum
// of numerical Strings
static void precomputePrefix(char[] str,
int n)
{
pref[0] = str[0] - '0';
for (int i = 1; i < n; i++)
pref[i] = pref[i - 1] +
toDigit(str[i]);
}
// Function to return the i-th
// term of Triangular Number
static int triangularNumber(int i)
{
int res = i * (i + 1) / 2;
return res;
}
// Function to return the sum
// of all resulting Strings
static int sumOfSubStrings(String str)
{
int n = str.Length;
// Precompute powers of 10
powerOf10();
// Precompute prefix sum
precomputePrefix(str.ToCharArray(), n);
// Initialize result
int ans = 0;
for (int i = 0; i < n - 1; i++)
{
// Apply the above general
// formula for every i
ans += (pref[n - i - 2] * (i + 1) +
toDigit(str[n - i - 1]) *
triangularNumber(n - i - 1)) *
power[i];
}
// Return the answer
return ans;
}
// Driver Code
public static void Main(String[] args)
{
String str = "1234";
// Function Call
Console.Write(sumOfSubStrings(str));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program for the
// above approach
var N = 10;
var pref = new Array(N).fill(0);
var power = new Array(N).fill(0);
// Function to convert a
// character to its equivalent
// digit
function toDigit(ch) {
return ch - "0";
}
// Function to precompute
// powers of 10
function powerOf10() {
power[0] = 1;
for (var i = 1; i < N; i++)
power[i] = power[i - 1] * 10;
}
// Function to precompute prefix sum
// of numerical Strings
function precomputePrefix(str, n) {
pref[0] = str[0] - "0";
for (var i = 1; i < n; i++)
pref[i] = pref[i - 1] + toDigit(str[i]);
}
// Function to return the i-th
// term of Triangular Number
function triangularNumber(i) {
var res = parseInt((i * (i + 1)) / 2);
return res;
}
// Function to return the sum
// of all resulting Strings
function sumOfSubStrings(str) {
var n = str.length;
// Precompute powers of 10
powerOf10();
// Precompute prefix sum
precomputePrefix(str.split(""), n);
// Initialize result
var ans = 0;
for (var i = 0; i < n - 1; i++) {
// Apply the above general
// formula for every i
ans +=
(pref[n - i - 2] * (i + 1) +
toDigit(str[n - i - 1]) *
triangularNumber(n - i - 1)) *
power[i];
}
// Return the answer
return ans;
}
// Driver Code
var str = "1234";
// Function Call
document.write(sumOfSubStrings(str));
</script>
Producción:
680
Complejidad de tiempo: O(N), donde N es la longitud de la string.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ashishsonam00 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA