Notice that the number 123456789 is a 9-digit number consisting exactly the numbers from 1 to 9, with no duplication. Double it we will obtain 246913578, which happens to be another 9-digit number consisting exactly the numbers from 1 to 9, only in a different permutation. Check to see the result if we double it again!
Now you are suppose to check if there are more numbers with this property. That is, double a given number with k digits, you are to tell if the resulting number consists of only a permutation of the digits in the original number.
Input Specification: Each input contains one test case. Each case contains one positive integer with no more than 20 digits.
Output Specification: For each test case, first print in a line "Yes" if doubling the input number gives a number that consists of only a permutation of the digits in the original number, or "No" if not. Then in the next line, print the doubled number.
Sample Input: 1234567899 Sample Output: Yes 2469135798
给你一个正整数A,长度 <= 20,问,如果把它加倍,得到数字B,==问B是不是 仅仅是组成A的那些数字的另一种排列方式==。
比如 123456789 加倍后是 246913578,它只是这些数字换了个顺序,所以它是。 比如 123 加倍后 是 456 ,很明显不是 再比如 900 加倍后是 1800,长度都超出了,很明显不是
0-9
,那么我只需要用一个大小为10的数组存储0-9每个数字出现的次数就可以,如果加倍后只是换了一种排列方式,那么0-9每个数字出现的次数肯定是不变的。A
中0-9
出现的次数,B
中0-9
出现的次数?可以,但没必要,我们只需要一个数组book10]
,统计A时,0-9出现的次数++,统计B时,0-9出现的次数--,==最后遍历数组book
,如果某个位置值不为0,B一定不只是A的另一种排列。==#include <iostream>
#include <cstring>
using namespace std;
int main() {
// 每一个位置上数字都是0-9,用一个数组保存0-9各出现了多少次
// 不用为统计a创建一个数组,统计b再创建一个数组,只要用一个数组
// 统计a时,对应位置++,统计b时,对应位置--,
// 最后遍历数组,某个位置不为0,或者2a最高位有进位,说明2a不是a的另一种排列,输出"No"
int book[10] = {0};
// 十进制数字,最长20位,用int 和 long long都无法存储
// 用字符存储
char num[21]; //
scanf("%s", &num);
int len = strlen(num);
// 统计原数各个位置 0-9各出现多少次
for (int i = 0; i < len; ++i) {
book[num[i] - '0']++;
}
// double原数,carry是进位,这个循环执行完后carry是原数字最高位的进制,若它不为0说明加倍后数字变长了肯定不合题意
int carry = 0;
for (int i = len - 1; i >= 0; --i) {
int temp = 2 * (num[i] - '0') + carry;
num[i] = temp % 10 + '0';
carry = temp / 10;
}
// 统计double后,0-9各出现多少次
for (int i = 0; i < len; ++i) {
book[num[i] - '0']--;
}
// 判断加倍后的数字是否只是原数字的另一种排列
bool flag = false;
for (int i = 0; i < 10; ++i) {
if (book[i] != 0) {
flag = true;
break;
}
}
// 不要漏了最高位进位的情况
printf("%s\n", flag || carry ? "No" : "Yes");
// 输出加倍后的数字,如果最高位进位了也要输出
if (carry) printf("%d", carry);
for (int i = 0; i < len; ++i)
printf("%d", num[i]);
return 0;
}
上面的代码我是为了把整个过程表示的清清楚楚,但其实 步骤 2 - 3 - 4可以合并到一个for循环完成,合并完那是相当的好看呐。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
int book[10] = {0};
// 十进制数字,最长20位,用int 和 long long都无法存储
// 用字符存储
char num[21]; //
scanf("%s", &num);
int len = strlen(num);
// carry是进位,这个循环执行完后carry是原数字最高位的进制,若它不为0说明加倍后数字变长了肯定不合题意
int carry = 0;
for (int i = len - 1; i >= 0; --i) {
// 统计 A 各个位置 0-9各出现多少次
int temp = num[i] - '0';
book[temp]++;
// 加倍转换为B
temp = temp * 2 + carry;
// 当前位置保留对10取余
num[i] = temp % 10 + '0';
// 向前进位
carry = temp / 10;
// 统计 B 各个位置 0-9各出现多少次
book[num[i] - '0']--;
}
// 判断加倍后的数字是否只是原数字的另一种排列
bool flag = false;
for (int i = 0; i < 10; ++i) {
if (book[i] != 0) {
flag = true;
break;
}
}
// 不要漏了最高位进位的情况
printf("%s\n", flag || carry ? "No" : "Yes");
// 输出加倍后的数字,如果最高位进位了也要输出
if (carry) printf("%d", carry);
printf("%s", num);
return 0;
}