給定數字字串的所有字首的和

---

在這個問題中，我們需要找到給定字串的所有字首的和。

最佳解決方案方法是遍歷字串的每個字首並將它們加起來以獲得答案。

問題陳述 - 我們給定一個名為 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) 以儲存字串字首。

我們可以在遍歷字串時獲取字串的每個字首。解決方案的主要邏輯部分是求和函式，以獲取兩個字串數字的和。程式設計師可以嘗試獲取給定字串所有後綴的和。