C++ 通过在从后往前的交替索引上逐渐添加自然数来找到下一个数字

如果我们要存储一个巨大的整数值，可以使用数值字符串来存储数字的值。如我们所知，不能使用int类型的数据类型在计算机中存储大于32位的数字。为了避免溢出的情况，在这个问题中，我们将使用数值字符串作为输入，而不是int变量，以便我们可以在更大范围的数字上解决这个问题。

问题陈述

现在，在这个问题中，我们需要通过在从后往前的交替索引上逐渐添加自然数来找到下一个数字。我们将获得一个数值字符串，并将最终的输出作为字符串本身返回。让我们看看如何解决这个问题。

让我们通过一些示例来理解这个问题。

输入 − s = “12345678”

输出 − 16375879

解释 −

• 首先，我们将最后一位数‘8’与第一个自然数‘1’相加。我们将得到(8 + 1) = 9作为新的数值字符串的最后一位数字。

• 然后我们将‘7’保持不变，因为我们要交替执行操作。

• 接下来，我们将取‘6’并将第二个自然数‘2’相加。我们将得到(6 + 2) = 8作为新数值字符串的第三个数字。

• 然后我们将‘5’保持不变，因为我们要交替执行操作。

• 下一步，我们将取‘4’并将第三个自然数‘3’相加。我们将得到(4 + 3) = 7作为新数值字符串的第五个数字。

• 然后我们将‘3’保持不变，因为我们要交替执行操作。

• 接下来，我们将取‘2’并将第四个自然数‘4’相加。我们将得到(2 + 4) = 6作为新数值字符串的第七个数字。

• 然后我们将‘1’保持不变，因为我们要交替执行操作。

• 因此，我们将得到最终的数值字符串为“16375879”

输入 − : s = “78930”

输出 − 18231

解释 −

• 首先，我们将最后一位数字‘0’与第一个自然数‘1’相加。我们得到（0 + 1）= 1作为新的数字字符串的最后一位数字。

• 然后，我们将‘3’保持不变，因为我们要交替进行操作。

• 接下来，我们将‘9’与第二个自然数‘2’相加。我们得到（9 + 2）= 11。

• 现在，我们需要将这个数字转换为一个位数，我们可以通过将它取模9来轻松做到这一点，这将给我们‘2’作为新的数字字符串的第三位数字。

• 然后，我们将‘8’保持不变，因为我们要交替进行操作。

• 接下来，我们将‘7’与第三个自然数‘3’相加。我们得到（7 + 3）= 10。

• 现在，我们需要将这个数字转换为一个位数，我们可以通过将它取模9来轻松做到这一点，这将给我们‘1’作为新的数字字符串的第五位数字。

• 因此，我们将得到最终的数字字符串“18231”。

问题解释

让我们试着理解这个问题并找到解决方法。在这个问题中，我们被给定一个数字字符串，我们必须根据以下条件修改字符串：

• 从1开始，以这种方式在位于奇数位置的数字上不断加上自然数，直至无穷大。

• 这意味着如果我们将最后一位设置为第一个位数（索引1），我们将修改位于奇数位置的数字，其余位数保持不变。

• 如果我们在相加后得不到一个个位数，我们应该不断地将这个数加到它变成一个个位数，或者我们可以使用另一种方法，即将修改后的数字取模9，这将给出相同的值，并且可以在更短的时间内得到一个个位数。

在下面的文章中，我们将通过在C ++中给出的简单代码中的注释来理解这种简单的方法。

解决方案算法

• 定义一个临时数字，并将addNum初始化为‘0’。

• 定义一个空字符串，用于包含最终输出。

• 从字符串的末尾开始循环，并将字符转换为整数。

• 如果该数字位于偶数位置，则为不同的数字从1到无穷大进行求和。

• 将求和后的数字转换为个位数。

• 将数字转换为字符。

• 将字符追加到最终输出字符串中。

示例：C++代码实现

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

// Function to find the next number by adding natural numbers in order on alternating indices from last
string Helper(string s){
   // Define a temporary integer 
   // Initialize the number we will add in the numeric string integers by 0
   int temp = 0, addNum = 0;
   // Define the empty string ans
   string ans = "";
   // Store the length of the numerical string
   int n = s.size();
   // Start the loop to get the new string
   for (int i = n - 1; i >= 0; i--) {
      // Store the digit at ith position in the integer form rather character form
      int num = s[i] - '0';
      // Check if the position is even or not, if even alter the digit
      if (temp % 2 == 0) {
         addNum += 1;
         num += addNum;
         // Check if the digit becomes greater than or equal to 10
         if (num >= 10) {
            // If yes, we need to take a modulus of 9 to make it single digit
            num %= 9;
            // Check if the single digit is 0, and change the digit back to 9
            if (num == 0)
            num = 9;
         }
      }
      // Store the result
      ans = to_string(num) + ans;
      temp += 1;
   }
   // Return the result
   return ans;
}
int main(){
   // Give the input string of numerical
   string s = "12345678";
   // Call the Helper function
   cout << "The following number by adding natural numbers in order on alternating indices on the string " << s << " from the last is: "<< Helper(s);
   return 0;
}

输出

The following number by adding natural numbers in order on alternating indices on the string 12345678 from the last is: 16375879

以上代码的复杂性

• 时间复杂度 – O(n);其中n是字符串的长度

• 空间复杂度 – O(1);我们在上面的代码中没有存储任何变量在某个数据结构中。

结论

在本文中，通过在最后的交替索引上按顺序相加自然数来找到以下数字。我们通过在最后的交替数字上应用操作并保持剩余数字不变来得到解决方案。我们将使用数字的字符串而不是实际数字，以便我们可以处理具有更多和更多数字的大值数字。