查詢一個數字，使其與 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) 以儲存結果字串。

我們已經學習瞭如何在輸出中找到任何字串，以便該字串與給定字串的和變為迴文。但是，我們使用了基本的數學方法來進行兩個字串的減法。程式設計師可以嘗試解決找到最接近給定字串的字串的問題，使得這兩個字串的和變為迴文。