We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital. The product 7254 is unusual, as the identity, 39*186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital. Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital. HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
* 根据题意分析： * 因为A*B=C，而且A、B不能等于1，所以C>B,C>A。 * A的位数+B的位数+C的位数=9，所以C大于3位，C>=1000。 * A的位数+B的位数=9-C的位数，若C为4位，则有两种组合(A为1位，B为4位；A为2位，B为3位)可以满足。 * 若C为5位，则A的位数+B的位数=4，不可能满足A*B=C的条件。 * * 所以C的范围为（1000-9999） * A/B的范围为(2-4999),因为A、B位置可互换， * 所以A的取值范围可确定(2-99),B的取值范围(100-4999)
import java.util.ArrayList; import java.util.List; public class Problem32 { //判断这三个数能否组成1-9的全数码。利用list来比较，list初始化了1-9的数字。 static boolean isPandigital(int a,int b,int c){ boolean flag = false; List<Integer> list = new ArrayList<Integer>(); for(int i=1;i<=9;i++) list.add(i); //将这三个数的所有组成从list中去除，list为空，则返回ture if (remove(a,list)&&remove(b,list)&&remove(c,list)&&list.size()==0) flag = true; return flag; } //看list中是否包含该数的组成数，如果有，从list中去除，返回true。 static boolean remove(int number,List<Integer> list){ char[] numberChar = String.valueOf(number).toCharArray(); for(char ch:numberChar){ int tempNumber = ch-'0'; if(list.size()>0&&list.contains(tempNumber)){ list.remove(Integer.valueOf(tempNumber)); }else{ return false; } } return true; } public static void main(String[] args) { long beginTime = System.currentTimeMillis(); int sum = 0; //相除 for(int i=1000;i<=9999;i++){ for(int j=2;j<=4999;j++){ if(i%j==0){ int k = i/j; if(isPandigital(i,j,k)){ System.out.println("i:"+i+" j:"+j+" k:"+k); sum += i; break; } } } } /** 相乘 //640ms for(int i=2;i<=99;i++){ for(int j=100;j<=4999;j++){ int k = i*j; if(isPandigital(k,i,j)){ System.out.println("i:"+i+" j:"+j+" k:"+k); sum += k; break; } } } */ System.out.println("sum==="+sum);//45228 long endTime = System.currentTimeMillis(); System.out.println(endTime-beginTime+"ms");//800ms } }
