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.
[编程题]Have Fun with Numbers (20)
- 热度指数：2289 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 640M，其他语言1280M
- 算法知识视频讲解
输入描述:
Each input file contains one test case. Each case contains one positive integer with no more than 20 digits.
输出描述:
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.
示例1
输入
1234567899
输出
Yes<br/>2469135798
在Java中，int和long数字长度都小于20位，所以必须用BigInteger
import java.math.BigInteger;
import java.util.Scanner;
/*
* 只能用BigInteger
*/
public class Main {
public static void main(String[] args) {
int[] count=new int[10];
Scanner sc=new Scanner(System.in);
String oriStr=sc.next();
BigInteger ori=new BigInteger(oriStr);
sc.close();
BigInteger newDig =ori.multiply(new BigInteger("2"));
String newStr=newDig.toString();
if(oriStr.length()!=newStr.length()){
System.out.println("No");
System.out.println(newStr);
return;
}
for(int i=0;i<oriStr.length();i++){
count[oriStr.charAt(i)-'0']++;
}
for(int i=1;i<newStr.length();i++){
count[newStr.charAt(i)-'0']--;
if(count[newStr.charAt(i)-'0']<0){
System.out.println("No");
System.out.println(newStr);
return;
}
}
System.out.println("Yes");
System.out.println(newStr);
}
}
发表于 2017-10-19 10:46:47
回复(0)
更多回答
#include <iostream>
#include <cstring>
using namespace std;
int num[10]={0},ansnum[10]={0};
int main(){
char s[25],ans[25];
cin>>s;
int len=strlen(s),carry=0,n=0; //carry是进位，n为积的位数
for(int i=len-1;i>=0;i--){ //从低位开始运算
num[s[i]-'0']++; //hash法记录数字出现个数
int temp=(s[i]-'0')*2+carry;
ansnum[temp%10]++;
ans[n++]=temp%10+'0'; //个位作为结果
carry=temp/10; //高位作为新进位
}
while(carry!=0){ //高位多余的进位直接补作积的高位
ansnum[carry%10]++;
ans[n++]=carry%10+'0';
carry/=10;
}
int flag;
for(flag=0;flag<10;flag++){ //对比原数和积各个数字出现次数
if(num[flag]!=ansnum[flag]) break;
}
if(flag!=10) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
for(int i=n-1;i>=0;i--)
cout<<ans[i];
return 0;
}
发表于 2018-02-23 13:36:16
回复(2)
import java.math.BigInteger;
import java.util.Scanner;
//因为只要翻倍一次，单独再写方法反而麻烦，考虑到本体复杂度低，以速度解题优先
//因为最大20位，Long最大18位，为了稳妥直接biginteger
public class Main {
public static void main(String[] args) {
Scanner in=new Scanner(System.in);
String s=in.nextLine();
BigInteger n=new BigInteger(s);
int a[]=new int[10];
int b[]=new int[10];
for(int i=0;i<s.length();i++){
a[(int)(s.charAt(i)-'0')]++;
}
BigInteger n2=(n.multiply(new BigInteger("2")));
s=String.valueOf(n2);
for(int i=0;i<s.length();i++){
b[(int)(s.charAt(i)-'0')]++;
}
Boolean f=true;
for(int i=0;i<10;i++){
if(a[i]!=b[i]){
f=false;
break;
}
}if(f){
System.out.println("Yes");
}else System.out.println("No");
System.out.println(s);
}
}
发表于 2016-10-29 11:27:53
回复(0)
思路：简略的大数乘法器。
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <map>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
string Double(string str)
{
string rlt;
int carry = 0;
for(int i = str.size() - 1; i>=0; i--)//从小到大
{
if((str[i] - '0')*2 <9)
{
rlt += '0' + (str[i] - '0') * 2 + carry;
carry = 0;
}
else
{
rlt += '0' + (str[i] - '0') * 2 - 10 + carry ;
carry = 1;
}
}
if(carry == 1)
rlt += '1';
reverse(rlt.begin(), rlt.end());
return rlt;
}
int main(int argc, char** argv) {
string str,str2;
cin >> str;
str2 = str;
bool check = false;
int a[10] = {0}; // 统计字符个数
int b[10] = {0};
for(int i = 0; i<3; i++)
{
str2 = Double(str2);
if(str2.size() != str.size())
{
break;
}
for(int j = 0; j<str.size(); j++)
{
a[str[j] - '0'] ++;
b[str2[j] - '0'] ++;
}
for(int j = 0; j<10; j++)
{
if(a[j] != b[j])
{
break;
}
if(j == 9)
{
check = true;
}
}
if(check)
{
cout << "Yes" << endl;
cout << str2 << endl;
break;
}
}
if(!check)
{
cout << "No" << endl;
cout << Double(str) << endl;
}
return 0;
}
发表于 2018-08-19 23:51:06
回复(0)
发表于 2018-08-06 12:02:07
回复(0)
大数问题，有些小的点很恶心，提交了好多次才过～～～
#include<stdio.h>
#include<string>
#include<iostream>
using namespace std;
int main()
{
string input;
cin>>input;
int N = input.size();
int *bigdata = new int[input.size()];
int *result = new int[input.size()];
int *origin = new int[10];
int *check = new int[10];
for(int i=0;i<10;i++)
{
check[i] = 0;
}
for(int i=0;i<10;i++)
{
origin[i] = 0;
}
for(int i=0;i<input.size();i++)
{
bigdata[i]=input[i]-48;
}
bool jinwei = false;
for(int i=N-1;i>=0;i--)
{
origin[bigdata[i]]++;
int tmp = 0;
if(jinwei)
tmp = bigdata[i]*2+1;
else
tmp = bigdata[i]*2;
if(tmp>=10)
{
if(i==0)
{
result[i]=tmp;
cout<<"No"<<endl;
//cout<<"1";
for(int i=0;i<N;i++)
{
cout<<result[i];
}
cout<<endl;
return 0;
}
jinwei= true;
tmp=tmp%10;
}
else
jinwei = false;
result[i]=tmp;
}
//check it
for(int i=0;i<N;i++)
{
check[result[i]]++;
}
for(int i=0;i<10;i++)
{
if(origin[i]!=check[i])
{
cout<<"No"<<endl;
for(int i=0;i<N;i++)
{
cout<<result[i];
}
cout<<endl;
return 0;
}
}
cout<<"Yes"<<endl;
for(int i=0;i<N;i++)
{
cout<<result[i];
}
cout<<endl;
return 0;
}
发表于 2018-03-01 15:34:29
回复(0)
#include<stdio.h>
//20位太大，用字符串处理
int bijiao(int ax[],int bx[],int length)
{
int i,j,flag=0;
int c[length+1];
for(i=0;i<=length;i++) c[i]=bx[i];
if(c[0]==1){
return 0;//double后的数字首位为1的话，数字个数肯定超出
}
for(i=0;i<length;i++){
for(j=1;j<=length;j++){
if(ax[i]==c[j]){
c[j]=-1;
flag =1;
break;
}//在c中依次查找a的元素，找到即将c中元素替换为-1
}
if(flag==0) return 0;//找不到即返回0
}
for(j=1;j<length;j++){
if(c[j]!=-1){
return 0;
}//感觉这段不要也可以。检查c除第一个元素外是否全部是-1.好吧的确可以不检查
}
return 1;
}
int main(void)
{
char s[20];
int a[20];
int b[21];
int i=0,j;
while((s[i]=getchar())!='\n') i++;
for(j=0;j<i;j++){
a[j]=(s[j]-'0');//将字符串转化为数组
}
for(j=1,b[0]=0;j<=i;j++){
b[j]=2*a[j-1];
if(b[j]>=10){
b[j]=b[j]%10;
b[j-1]++;//double a[n],得到b[n+1]，b[0]为进位预留
}
}
if(bijiao(a,b,i)){
printf("Yes\n");
}
else printf("No\n");
if(b[0]==1) for(j=0;j<=i;j++) printf("%d",b[j]);
else for(j=1;j<=i;j++) printf("%d",b[j]);//根据是否有进位，选择从b[0]或b[1]开始输出
return 0;
}
发表于 2017-06-23 23:45:50
回复(0)
来个C++的吧
#include <iostream>
#include<string>
#include <map>
using namespace std;
string Strmulit(string s, int n)
{
string res;
bool sta = false;
int pre = 0, i = s.length() - 1, sum;
for (; i >= 0; i--)
{
sum = s[i] - '0';
sum = sum * n;
if (pre != 0)
{
sum += pre;
pre = 0;
}
if (sum > 9)
{
pre = sum / 10;
sum = sum % 10;
}
char ch = sum + '0';
res = ch + res;
}
if (pre != 0)
{
char ch = pre + '0';
res = ch + res;
}
return res;
}
int main()
{
string num;
int two = 2;
while (cin >> num)
{
string res = Strmulit(num, two);
map<char, int> data;
for (auto c : num)
data[c]++;
for (auto c : res)
data[c]--;
bool sta = true;
for (map<char, int>::iterator it = data.begin(); it != data.end(); it++)
if (it->second != 0)
{
sta = false;
break;
}
if (true == sta)
cout << "Yes" << endl << res << endl;
else
cout << "No" << endl << res << endl;
}
return 0;
}
发表于 2017-04-28 21:10:24
回复(0)
这种题好烦😂
#include<bits/stdc++.h>
using namespace std;
struct bign {
int d[100];
int len;
bign() {
memset(d,0,sizeof(d));
len=0;
}
};
bign change(string str) {
bign a;
a.len=str.size();
for(int i=0; i<a.len; i++) {
a.d[i]=str[a.len-1-i]-'0';
}
return a;
}
bign mul(bign a,int b) {
bign c;
int carry=0;
for(int i=0; i<a.len; i++) {
int temp=a.d[i]*b+carry;
c.d[c.len++]=temp%10;
carry=temp/10;
}
while(carry!=0) {
c.d[c.len++]=carry%10;
carry/=10;
}
return c;
}
bool compare(bign a,bign b) {
if(a.len!=b.len) {
return 0;
} else {
int count[a.len]= {0};
for(int i=0; i<a.len; i++) {
count[a.d[i]]++;
}
for(int i=0; i<b.len; i++) {
count[b.d[i]]--;
}
for(int i=0; i<a.len; i++) {
if(count[a.d[i]]) {
return 0;
}
}
return 1;
}
}
void Printf(bign a) {
for(int i=a.len-1; i>=0; i--) {
cout<<a.d[i];
}
}
int main() {
string str;
cin>>str;
bign a=change(str);
bign b=mul(a,2);
if(compare(a,b)) {
cout<<"Yes"<<endl;
} else {
cout<<"No"<<endl;
}
Printf(b);
}
发表于 2022-11-16 21:36:08
回复(0)
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int main(){
char ss[22];
char cc[22];
char res[22];
cin>>ss;
strcpy(cc,ss);
int flag=1;
if(ss[0]>='5'){
flag=0;
ss[0]-=5;
}
//乘2运算
for(int i=strlen(ss)-1;i>=0;i--){
ss[i]=(ss[i]-'0')*2+'0';
}
for(int i=strlen(ss)-1;i>=0;i--){
while(ss[i]>'9'){
ss[i-1]++;
ss[i]-=10;
}
}
//直接复制字符串然后排序 比较
strcpy(res,ss);
sort(ss,ss+strlen(ss));
sort(cc,cc+strlen(cc));
if(strcmp(cc,ss)==0&&flag==1) cout<<"Yes";
else cout<<"No";
cout<<endl;
if(flag==0) cout<<"1";
cout<<res;
}
编辑于 2020-06-23 18:57:25
回复(0)
这题我刚做的思路就有错误，应该把乘积之后的数反过来存储，这样就不用担心最前面一个数进位的问题了，用了两个int数组，下标即是0-9，值为出现的个数，保存乘积前和乘积后0-9的个数，判断两个数构成的数字是否完全一致。参考的Relaxing大佬的
#include<iostream>
#include<stdlib.h>
#include<string.h>
using namespace std;
char s[25], ss[25];
int ans[10] = { 0 }, ans1[10] = {0};
int n = 0, tem = 0, carry = 0, j = 0, flag = 0;//字符的总数，临时接受*2的结果，进位,
int main() {
cin >> s;
n = strlen(s);
for (int i = n - 1; i >= 0; i--) {
ans[s[i] - '0']++;//把乘积之前的数字作为索引，值表示数字的个数
tem = (s[i] - '0') * 2 + carry;
ans1[tem % 10]++;//表示乘2之后数的个数存入ans1，用来与前面一个ans数组对比
ss[j++] = (tem % 10) + '0';//低位加入ss
carry = tem / 10;//进位赋给carry
}
while (carry != 0) {//表示第一个数还有进位
ans1[carry % 2]++;
ss[j++] = (carry % 2)+'0';//把进位加入ss
carry /= 10;
}
for (flag; flag < 10; flag++) {
if (ans[flag] != ans1[flag])break;
}
if (flag != 10)cout << "No" << endl;
else cout << "Yes" << endl;
for (int i = j - 1; i >= 0; i--)cout << ss[i];
cout << endl;
system("pause");
return 0;
}
发表于 2019-10-07 09:35:46
回复(0)
package temp;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
public class test {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
char[] s=sc.next().toCharArray();
HashMap<Character,Integer> set=new HashMap<>();
for(int i=0;i<s.length;i++) {
if(set.containsKey(s[i])) {
set.put(s[i], set.get(s[i])+1);
}else {
set.put(s[i], 1);
}
}
String c="";
int d=0;
for(int i=s.length-1;i>=0;i--) { //高精度加法
int sum=(s[i]-'0')*2+d;// System.out.println(sum);
c=(sum%10)+c;
d=sum/10;
}
if(d!=0)
c=d+c;
// System.out.println(c);
HashMap<Character,Integer> hs=new HashMap<>();
for(int i=0;i<c.length();i++) {
char t=c.charAt(i);
if(hs.containsKey(t))
hs.put(t,hs.get(t)+1);
else
hs.put(t, 1);
}
boolean f=true;
for(int i=0;i<c.length();i++) {
char t=c.charAt(i);
if(!set.containsKey(t)) {
f=false;
break;
}else {//同一个数字只能出现相同的次数
int a=set.get(t);
int b=hs.get(t);
if(a!=b) {
f=false;
break;
}
}
}
if(f)
System.out.println("Yes");
else System.out.println("No");
System.out.println(c);
}
}
发表于 2019-08-18 09:22:29
回复(0)
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string s;
string tmp;
bool judge() {
int last = 0;
int flag1 [10] = {0};
int flag2 [10] = {0};
for(int i = s.size() - 1; i >= 0; --i) {
int t = (s[i] - '0')*2 + last;
tmp += (t % 10) + '0';
last = t / 10;
flag1[s[i] - '0'] += 1;
flag2[t % 10] += 1;
}
if (last == 1) {
tmp += '1';
return false;
}
for(int i = 0; i <10; ++i) {
if(flag1[i] != flag2[i]) {
return false;
}
}
return true;
}
int main() {
cin >> s;
cout << (judge() ? "Yes" : "No") << endl;
reverse(tmp.begin(), tmp.end());
cout << tmp << endl;
}
#include <string>
#include <algorithm>
using namespace std;
string s;
string tmp;
bool judge() {
int last = 0;
int flag1 [10] = {0};
int flag2 [10] = {0};
for(int i = s.size() - 1; i >= 0; --i) {
int t = (s[i] - '0')*2 + last;
tmp += (t % 10) + '0';
last = t / 10;
flag1[s[i] - '0'] += 1;
flag2[t % 10] += 1;
}
if (last == 1) {
tmp += '1';
return false;
}
for(int i = 0; i <10; ++i) {
if(flag1[i] != flag2[i]) {
return false;
}
}
return true;
}
int main() {
cin >> s;
cout << (judge() ? "Yes" : "No") << endl;
reverse(tmp.begin(), tmp.end());
cout << tmp << endl;
}
发表于 2019-04-15 18:14:05
回复(0)
from collections import Counter
num=raw_input()
permutation,dn=Counter(num),2*int(num)
np=Counter(str(dn))
print 'Yes' if np==permutation else 'No'
print dn
num=raw_input()
permutation,dn=Counter(num),2*int(num)
np=Counter(str(dn))
print 'Yes' if np==permutation else 'No'
print dn
水题
发表于 2019-01-17 11:06:26
回复(0)
lst = ['0','1','2','3','4','5','6','7','8','9']
n = input()
n = int(n)
m = 2*n
nlst,mlst = [],[]
for i in str(n):
nlst.append(i)
for i in str(m):
mlst.append(i)
countn,countm = [],[]
for i in lst:
countn.append(nlst.count(i))
countm.append(mlst.count(i))
boo = True
for i in range(0,len(lst)):
if countn[i]!=countm[i] or (countn[i]==0 and countm[i]!=0) or (countn[i]!=0 and countm[i]==0):
print("No")
print(str(m))
boo = False
break
if boo:
print("Yes")
print(str(m))
办法比较笨，直接数出数再进行比较
发表于 2018-12-06 20:07:20
回复(0)
#include <iostream>
#include<sstream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int main() {
string str;
char out[22]={'\0'};
cin>>str;
int carry=0,flag=1;
int num[10]={0};
int j=0;
for(int i=str.length()-1;i>=0;i--)
{
int t=str[i]-'0';
num[t]++;
out[j++]=(t*2+carry)%10+'0';
carry=(t*2+carry)/10;
num[(t*2+carry)%10]--;
}
if(carry==1) out[j++]=carry+'0';
for(int i=0;i<10;i++)
if(num[i]!=0) {flag=0;break;}
if(!flag) cout<<"No"<<endl;
else {cout<<"Yes"<<endl;}
reverse(out,out+strlen(out));
printf("%s\n", out);
}
发表于 2018-06-08 14:04:19
回复(0)
#include <iostream>
using namespace std;
char a[20];//原始数据
int num[20];//原始数据转化为整形
int b[25];//2倍后数据
int flag = 0;//进位标志位
int array[10] = {0};//判断两个数组是否相等
bool out;//输出结果标志位
int main()
{
int length;//输入数组长度
cin >> a;//输入
for (int i = 0; i < 20; i++)//转为整形
{
if (a[i] - '0' >= 0 && a[i] - '0'<='9')//确定字符串长度
num[i] = a[i] - '0';
else
{
length = i;
break;
}
}
for (int i = length; i >= 0; i--)//遍历数组 计算出二倍数组
{
b[i] = num[i] * 2 + flag;
if (b[i]>9)
{
b[i] -= 10;
flag = 1;
}
else flag = 0;
}
//判断二倍数组是否符合条件
if (flag) out = false;//最高位存在进位
else
{
for (int i = 0; i < length; i++)//遍历数组
{
array[num[i]]++;
array[b[i]]--;
}
for (int i = 0; i < 10; i++)
if (array[i]) {//array数组存在不为0项
out = false;
break;
}
else out = true;
}
if (out) cout << "Yes" << endl;//输出结果
else cout << "No" << endl;
if (flag) cout << flag;//最高位存在进位，先输出1
for (int i = 0; i < length; i++)
cout << b[i];
cout << endl;
return 0;
}
发表于 2018-02-25 11:20:35
回复(0)
# -*- coding: utf-8 -*-
__author__ = 'Yaicky'
import sys
for line in sys.stdin:
origin_num = int(line.split()[0])
origin_cmp = line.split()[0]
origin_cmp = list(map(int, origin_cmp))
double_num = origin_num*2
double_cmp = list(map(int, str(double_num)))
origin_cmp = sorted(origin_cmp)
double_cmp = sorted(double_cmp)
# print (origin_cmp)
# print (double_cmp)
# print (double_cmp == origin_cmp)
if double_cmp == origin_cmp:
print("Yes")
print(double_num)
else:
print("No")
print(double_num)
'''
1234567899
'''
发表于 2017-10-11 21:53:51
回复(0)
对原数每位上的数进行排序，double后的数作同样处理，然后比较数组是否相同
#-*-coding:utf-8 -*-
while True:
try:
s=raw_input()
N=int(s)
D=2*N
p=[int(x) for x in s]
q=[int(y) for y in str(D)]
p.sort()
q.sort()
if p==q:print 'Yes'
else:print 'No'
print str(D)
except:
break
发表于 2017-07-23 14:35:10
回复(0)
问题信息
难度：
24条回答
3收藏
5804浏览
通过挑战的用户
-
2023-02-23 17:23:38 -
2023-02-23 01:15:25 -
2023-02-22 16:14:06 -
2023-02-16 16:12:06 -
2023-02-07 10:37:51
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
