给定数字字符串的所有前缀的和

---

在这个问题中，我们需要找到给定字符串的所有前缀的和。

最佳解决方案方法是遍历字符串的每个前缀并将它们加起来以获得答案。

问题陈述 - 我们给定一个名为 num_Str 的字符串，其中包含 N 位数字。我们需要找到给定字符串所有前缀的和。

示例

输入

num_str = "1123"

输出

1247

解释 - 给定字符串的所有前缀为 1、11、112 和 1123。所有前缀的和为 1247。

输入

num_str = "1000"

输出

1111

解释- 1 + 10 + 100 + 1000 = 1111

输入

num_str = "123456789";

输出

137174205

解释- 1 + 12 + 123 + 1234 + 12345 + 123456 + 1234567 + 12345678 + 123456789 = 137174205

方法 1

在这种方法中，我们将获取字符串的每个前缀，并将它的和存储在一个变量中。在这里，我们将实现一个函数来对两个字符串的数字求和以获得大字符串的和。

我们可以使用基本数学来对大字符串求和。

算法

步骤 1 - 将 'allPrefixSum' 初始化为 '0' 以存储所有前缀的和，并将 'prefix' 初始化为空字符串以存储当前前缀。

步骤 2 - 开始遍历字符串，并使用 '+=' 运算符将字符串的当前字符附加到 'prefix' 的末尾。

步骤 3 - 执行 twoDigitSum() 函数将 'prefix' 值添加到 'allPrefixSum' 值，并将函数的返回值存储在 'allPrefixSum' 变量中。

步骤 3.1 - 在 twoDigitSum() 函数中，num2 的长度应该大于 num1。如果不是，则交换这两个数字。

步骤 3.2 - 初始化字符串变量 sum_Str 以存储 num1 和 num2 的和。

步骤 3.3 - 反转 num1 和 num2 字符串以从第 0 个索引开始求和。在基本数学中，我们从末尾开始添加数字。

步骤 3.4 - 将 'car' 变量初始化为 0 以存储进位。

步骤 3.5 - 开始遍历 num1 字符串。从 num1 和 num2 的第 p 个索引获取字符，并将它们相加。此外，将进位添加到值中，并将最终值存储在 sum 中。

步骤 3.6 - 执行 sum % 10 运算，并将其附加到 sum_Str 字符串。在 'car' 存储中，存储 sum / 10。

步骤 3.7 - 现在，转换剩余的 num2 字符串。将第 p 个索引处的字符添加到 'car'，取其模 10，并将其附加到 sum_str 字符串。此外，通过 sum/10 更新 'car' 值。

步骤 3.8 - 如果 'car' 的值不为 0，则将其附加到 sum_Str。

步骤 3.9 - 反转 sum_str 值并从函数中返回它。

步骤 4 - 最后，返回 'allPrefixSum' 变量的值。

示例

#include <bits/stdc++.h>
using namespace std;

string twoDigitSum(string num1, string num2) {
   // We need num2's length larger
   if (num1.length() > num2.length())
      swap(num1, num2);
   // Stores resulting sum
   string sum_str = "";
   // Get size of strings
   int len1 = num1.length(), len2 = num2.length();
   // Reverse strings
   reverse(num1.begin(), num1.end());
   reverse(num2.begin(), num2.end());
   // variable to store car bit
   int car = 0;
   // Traverse num1
   for (int p = 0; p < len1; p++) {
      // Get the sum of digits at the pth index by adding the carry
      int sum = ((num1[p] - '0') + (num2[p] - '0') + car);
      // Update sum_str
      sum_str.push_back(sum % 10 + '0');
      // Update carry to use in the next step
      car = sum / 10;
   }
   // Need to add extra digits of len2
   for (int p = len1; p < len2; p++) {
      // Get the sum of digits, update sum_str, and carry
      int sum = ((num2[p] - '0') + car);
      sum_str.push_back(sum % 10 + '0');
      car = sum / 10;
   }
   // If carry is not 0, add it to sum_str
   if (car)
      sum_str.push_back(car + '0');
   // Reverse resultant string to get answer
   reverse(sum_str.begin(), sum_str.end());
   return sum_str;
}
string getPrefixSum(string num_str) {
   // To store the sum of prefixes
   string allPrefixSum = "0";
   // To store prefix
   string prefix = "";
   // Traverse the string
   for (int p = 0; p < num_str.length(); p++) {
      // Get prefix till pth index
      prefix += num_str[p];
      // Get prefix sum
      allPrefixSum = twoDigitSum(prefix, allPrefixSum);
   }
   // Return Answer
   return allPrefixSum;
}
int main() {
   string num_str = "1123";
   cout << "The sum of all prefixes of the given string is " << 
getPrefixSum(num_str);

   return 0;
}

输出

The sum of all prefixes of the given string is 1247

时间复杂度 - O(N*N) 以添加字符串的每个前缀。

空间复杂度 - O(N) 以存储字符串前缀。

我们可以在遍历字符串时获取字符串的每个前缀。解决方案的主要逻辑部分是求和函数，以获取两个字符串数字的和。程序员可以尝试获取给定字符串所有后缀的和。