Problem
Take the number 192 and multiply it by each of 1, 2, and 3:
192 x 1 = 192
192 x 2 = 384
192 x 3 = 576
By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).
What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?
分析
可以由一个整数 x 与(1,2,…,n)的乘积连接而成的,只含有不重复的1~9 九个数字的数。
设乘数为 x,相当于至少 x 的位数 + 2*x 的位数要 <= 9 。当x是5位数时,x的位数 + 2*x 的位数 肯定>9,不满足。
确定了乘数x的范围后,可以穷举遍历。对每一个x,用product记录乘积的连接字符串。判断product是否满足条件即可。
C\C++
方法1 【思路基本同Python方法1】使用vector容器保存数字,使用set容器去除重复数字。
split_digits(n,vector v)函数实现,将n的每一位数字,加入到容器v中。
乘数 x 从 1~10000遍历。对每一个x,做如下操作:
(1) 初始时split_digits(x,product),将x的各位数字保存到product中。n = 2
(2) 将n*x的各位数字加入到product容器中。
(3) 判断product的长度,如果=9,说明可能满足条件,继续判断是否只含有1~9 九个数字,将product保存到set中,利用set去除重复的值。如果去除重复后的长度和原长度相等,说明不存在重复的值,再判断这九个数字不含有0即表明只含有1~9。至此找到一个满足条件的数了。如果product的长度 >9,说明x不用试了,肯定不能满足了,break,进入x+1。
程序打印出了所有满足条件的数,数量不多,所以可以直接看出最大值。
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;
/************************************************************************
* 将n的各位数字,加入到v容器
* n = 123,则分别将1,2,3 push_back 到vector容器v中
************************************************************************/
void split_digits(int n, vector<int>& v)
{
assert(n>0);
int digits[12];
int len = 0;
while(n!=0)
{
digits[len++] = n %10;
n /= 10;
}
for(int i=len-1;i>=0;i--) //digits[]为逆序保存
{
v.push_back(digits[i]);
}
}
void disp(int n){ cout<<n; }
int main()
{
for(int x=1;x<10000;x++)
{
vector<int> product;
split_digits(x,product); //x的各位数字加入到product中
//for_each(product.begin(),product.end(),disp);
//cout<<endl;
int n = 2;
while(1)
{
split_digits(n*x,product); //n*x 的各位数字加入到product中
if (product.size() == 9)
{
set<int> set_product(product.begin(),product.end()); //将product中的数字保存到set集合中
if(set_product.size() == 9) //说明没有重复数字
{
//判断是否含有数字 0
set<int>::iterator it = set_product.find(0);
if (it == set_product.end()) //不含数字0
{
//product是一个满足条件的值,输出
cout<<"x="<<x<<" n="<<n<<" product=";
for_each(product.begin(),product.end(),disp);
cout<<endl;
}
}
}
else if (product.size() > 9)
{
break; //跳出循环,进入x+1
}
else{}
n++;
}
}
return 0;
}
Python
方法1 穷举判断
乘数 x 从 1~10000遍历。对每一个x,做如下操作:
(1) 初始时product=str(x),n = 2
(2) product += str(n*x)
(3) 判断product的长度,如果=9,说明可能满足条件,继续判断是否只含有1~9 九个数字,将product保存到set中,利用set去除重复的值。如果去除重复后的长度和原长度相等,说明不存在重复的值,再判断这九个数字不含有0即表明只含有1~9。至此找到一个满足条件的数了。判断找到的product是否最大,并记录最大到max_product中。如果product的长度 >9,说明x不用试了,肯定不能满足了,break,进入x+1。
max_x, max_product = 0, 0
for x in range(1, 10000):
product = str(x)
n = 2
while True:
product += str(n * x)
if len(product) == 9:
set_product = set(product) # set is used to remove the repeated digits
if len(set_product) == 9:
#find one candidate
#check if has '0'
if '0' in set_product:
pass
else:
print 'find one: x=', x, ' n=', n, ' product=', product
if int(product) > max_product:
max_x, max_product = x, int(product)
elif len(product) > 9:
break
else:
pass #do nothing, continue the loop
n += 1
print max_x, max_product
答案
932718654