当前位置:首页 » Project Euler » 详细页

Permuted multiples 题号:52 难度: 5 中英对照

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

Solution

使用暴力法即可求解,从1开始循环,取第一个数 $~x~$使得$~3x,4x,5x,6x~$和$~2x~$有相同的数字即可求解。 判读两个数是否有相同的数字只需要将其各位数数组进行排序,比较排序后的数组上的对应位置的数字是否相等。

Code

using System;
using System.Diagnostics;
using System.Linq;
namespace euler
{
	class Problem109
	{
		public static void Main(string[] args)
		{
			Stopwatch clock = Stopwatch.StartNew();
			var result = Run();
			clock.Stop();
			Console.WriteLine(result);
			Console.WriteLine("Solution took {0} ms", clock.Elapsed.TotalMilliseconds);
			Console.Read();
		}
		public static long Run()
		{
			int i = 1;
			while (true)
			{
				if (HasSameDigits(i)) return i;
				i++;
			}
		}
		private static bool HasSameDigits(int x)
		{
			char[] xdigits = (2 * x).ToString().ToCharArray();
			Array.Sort(xdigits);
			for (int i = 3; i <= 6; i++)
			{
				char[] ydigits = (i * x).ToString().ToCharArray();
				Array.Sort(ydigits);
				if (!xdigits.SequenceEqual(ydigits)) return false;
			}
			return true;
		}
	}
}
142857
Solution took 164.8783 ms
import java.util.Arrays;
public final class p052 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        long result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }	
    public static long run() {
        int i=1;
        while(true){
            if(hasSameDigits(i)) return i;
            i++;
        }        
    }
    
    private static boolean hasSameDigits(int x) {
        char[] xdigits = Integer.toString(2*x).toCharArray();
        Arrays.sort(xdigits);
        for(int i=3;i<=6;i++){
            char[] ydigits = Integer.toString(i*x).toCharArray();
            Arrays.sort(ydigits);
            if(!Arrays.equals(xdigits, ydigits)) return false;
        }
        return true;
    }
}
142857
90ms
import itertools
def Run():
    for i in itertools.count(1):
        digits = sorted(str(2*i))
        if all(sorted(str(i * j)) == digits for j in range(3, 7)):
            return i
def Main():
    from time import clock
    start = clock()
    result = Run()    
    finish = clock()
    print([start,finish])
    print(result)
    print( "{0}ms".format((finish-start)*1000))
Main()
142857
405.097084383ms