查找一个数字，使其与 N 的和为回文数

---

在这个问题中，我们将找到一个长度等于给定字符串的字符串，以便当我们将这两个字符串相加时，得到回文字符串。

在这里，我们可以找到另一个字符串，使得两者的和为 99999…，即相同长度的最大回文字符串。如果给定字符串以“9”开头，我们可以找到另一个字符串，使得两者的和为“11111…”。

问题陈述 – 我们给定一个包含数字字符的 num 字符串。我们需要找到相同长度的数字字符串（不含前导零），使得这两个字符串的和可以是一个回文字符串。

示例

输入

num = "9865";

输出

1246

解释 – 当我们对 9856 和 12446 求和时，得到 11111，这是一个回文字符串。

输入

num = "54534";

输出

45465

解释 – 54534 + 45465 的和为 99999。

输入

num = “5”

输出

4

解释 – 5 + 4 的和为 9。

方法 1

任何包含单个字符的字符串都将始终是回文字符串。这里，我们需要找到另一个相同长度的字符串。因此，我们可以找到一个字符串，使得我们得到长度为 N 的最大回文字符串或长度为 N + 1 的最小回文字符串。

每当给定字符串以“1”到“8”的数字开头时，我们将找到另一个字符串以得到结果和“9999..”，其长度等于 N。当给定字符串以“9”开头时，我们将找到另一个字符串，使得结果和变为长度为 N + 1 的“1111…”。

算法

步骤 1 – 初始化“temp”字符串以存储结果字符串。

步骤 2 – 如果给定字符串的第一个字符是“9”，则将长度 + 1 个“1”字符追加到 temp 字符串。之后，执行 getDifference() 函数以找到“temp”和给定字符串之间的差异并返回其值。

步骤 2.1 – 在 getDIfference() 函数中，初始化“diff”字符串以存储差异。

步骤 2.2 – 使用 reverse() 方法反转 num1 和 num2 字符串。

步骤 2.3 – 将“car”初始化为 0 以存储减法时的进位。

步骤 2.4 – 开始遍历 num2 字符串。从 num1[p] 字符中减去 num2[p] 和“car”的值，并将它们存储在“sub”变量中。

步骤 2.5 – 如果 sub 值为负，则向 sub 添加 10 并将“car”更新为 1。否则，将“car”更新为 0。

步骤 2.6 – 将“sub”值推入“diff”字符串。

步骤 2.7 – 最后，反转“diff”字符串并返回其值。

步骤 3 – 如果第一个字符介于“0”到“8”之间，我们需要找到另一个字符串，使得它与给定字符串的和变为“9999….”。

步骤 4 – 遍历给定字符串，并在从“9”中减去当前字符后将结果字符追加到“temp”字符串。

步骤 5 – 最后返回“temp”字符串。

示例

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

string getDifference(string num1, string num2) {
    string diff = ""; // To store difference of num1 and num2
    int len1 = num1.length(), len2 = num2.length();
    // Reverse strings
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    int car = 0;
    // Traverse numeric strings
    for (int p = 0; p < len2; p++) {
        // Getting a difference
        int sub = ((num1[p] - '0') - (num2[p] - '0') - car);
        // Basic subtraction logic
        if (sub < 0) {
            sub = sub + 10;
            car = 1;
        }
        else
            car = 0;
        // Push the sub in the string
        diff.push_back(sub + '0');
    }
    // Reverse the final string
    reverse(diff.begin(), diff.end());
    return diff;
}
string getNum(string num) {
    ll len = num.size();
    string temp = "";
    // When string starting with '9'
    if (num[0] == '9') {
        // Get string containing len + 1 '1' digits
        while (len--) {
            temp += '1';
        }
        temp += '1';
        return getDifference(temp, num);
    }
    // In other cases
    else {
        for (ll p = 0; p < len; p++) {
            // Get a string such that we can form the '999999999..' string
            temp += ((9 - (num[p] - '0')) + '0');
        }
        return temp;
    }
}
int main() {
    string num = "53242";
    cout << "We can get palindrome number by adding " << num << " and " << getNum(num) << ".\n";
    return 0;
}

输出

We can get palindrome number by adding 53242 and 46757.

时间复杂度 – O(N) 以获取两个字符串之间的差异。

空间复杂度 – O(N) 以存储结果字符串。

我们已经学习了如何在输出中找到任何字符串，以便该字符串与给定字符串的和变为回文。但是，我们使用了基本的数学方法来进行两个字符串的减法。程序员可以尝试解决找到最接近给定字符串的字符串的问题，使得这两个字符串的和变为回文。