查找一个数字,使其与 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) 以存储结果字符串。
我们已经学习了如何在输出中找到任何字符串,以便该字符串与给定字符串的和变为回文。但是,我们使用了基本的数学方法来进行两个字符串的减法。程序员可以尝试解决找到最接近给定字符串的字符串的问题,使得这两个字符串的和变为回文。