Euler Problem 52

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.

This one seemed pretty straight forward … and it was. The only thing I had to straighten out first was my Permutations routine. I created a custom class for it (given that its recursive) and then instantiated it in the Problem method. Nice and tidy.

import java.util.*;

public class Euler52
{
    public static void main(String[] args)
    {
        Euler52 e = new Euler52();
        System.out.format(“Problem: %s\n”, e.getClass().getName());
        System.out.format(“Answer = %s\n”, e.Problem());
    }
    public String Problem ()
    {
        ArrayList<String> P = new ArrayList<String>();
        Permutations p = new Permutations();
        int x = 0;
        for (int i = 100000; i <= 1000000; i++)
        {
            P = p.makePerms(Integer.toString(i));
            if (i % 5000 == 0)
                System.out.format(“%d\n”, i);
            if (P.contains(Integer.toString(2*i)))
                if (P.contains(Integer.toString(3*i)))
                    if (P.contains(Integer.toString(4*i)))
                        if (P.contains(Integer.toString(5*i)))
                            if (P.contains(Integer.toString(6*i)))
                            {
                                x=i;
                                break;
                            }
        }
        return String.valueOf(x);
    }
    public class Permutations
    {
        ArrayList<String> Perms = new ArrayList<String>();
        public ArrayList<String> makePerms (String s)
        {
            Perms.clear();
            p1(“”,s);
            return Perms;
        }
        public void p1(String prefix, String s)
        {
            int N = s.length();
            if (N == 0)
            {
                if (Perms.contains(prefix) == false)
                    Perms.add(prefix);
            }
            else
                for (int i = 0; i < N; i++)
                    p1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N));
        }
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s