CODEWITHSUNDEEP
javaperformance
Jazzy
Jazzy

Reputation: 89

Tips to solve problem #41 of project euler

I'm trying to solve Problem 41of project Euler in Java, by counting the number from 99888888 to 80000000(which took very long time :( ), I got 98765431 as an answer, but I'm getting that answer not correct. Could anyone please tell me the reason of not getting the correct answer and how can I speed my program?

Upvotes: 6

Views: 3576

Answers (4)

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56674

To obtain a solution in a "reasonable" time, you need the following observations based on the special property that a number is divisible by 3 if the sum of its digits is divisible by 3:

                            divisible by 
 1+2+3+4 = 10               -  
 1+2+3+4+5 = 15             3 
 1+2+3+4+5+6 = 21           3
 1+2+3+4+5+6+7 = 28         - 
 1+2+3+4+5+6+7+8 = 36       3 
 1+2+3+4+5+6+7+8+9 = 45     3

So, a "big" prime pandigital number has 4 or 7 digits. (a prime number bigger than 3 is not divisible by 3)

Because you want to obtain the biggest number, it's better to start with the 7-digit numbers and continue to check the 4-digit numbers only if the number was not found. For sure, a 4-digit number exists, because it is specified: 2143.

Now, a possible solution looks like this:

public class P41 {

    public static void main(String[] args) {

        boolean wasFound = false;

        for (int nr = 7654321; nr >= 1234567; nr -= 2) { // even != prime
            if (isPandigital(nr) && isOddPrime(nr)) {
                System.out.println(nr);
                wasFound = true;
                break;
            }
        }

        if (!wasFound) {
            /* not <=, because 1234 is even */
            for (int nr = 4321; nr > 1234; nr -= 2) {
                if (isPandigital(nr) && isOddPrime(nr)) {
                    System.out.println(nr);
                    break;
                }
            }
        }
    }

    private static boolean isOddPrime(int x) {
        int sqrt = (int) Math.sqrt(x);
        for (int i = 3; i <= sqrt; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }

    private static int getNumberOfDigits(int x) {
        int count = 0;
        while (x > 0) {
            count++;
            x /= 10;
        }
        return count;
    }

    private static boolean isPandigital(int x) {
        int numberOfDigits = getNumberOfDigits(x);
        Set<Integer> digits = new HashSet<Integer>();
        for (int i = 1; i <= numberOfDigits; i++) {
            digits.add(i);
        }
        for (int i = 1; i <= numberOfDigits; i++) {
            digits.remove(x % 10);
            x /= 10;
        }
        if (digits.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

}

Time: 8 ms.

Upvotes: 5

Gilbert Le Blanc
Gilbert Le Blanc

Reputation: 51515

Here is the problem statement:

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, 2143 is a 4-digit pandigital and is also prime. What is the largest n-digit pandigital prime that exists?

I wrote a program that started with 987654321 and counted down. I checked that the number was pandigital, and if it was, checked if it was prime.

It took 66 seconds on my Windows 8.1 computer to find the largest prime pandigital.

When I tested the other way around, first prime, then pandigital, the program took way longer than 66 seconds. I cancelled it.

When I applied GregS' tip about discounting all 9 digit and 8 digit pandigital numbers, and started counting down from 7654321, my brute force algorithm took 13 milliseconds.

Upvotes: 0

Cody
Cody

Reputation: 61

The only possible prime pandigital numbers are those with length 1, 4, & 7 because every other pandigital number has the sum of its digits divisible by 3.

So, you'd only need to test for 7! = 5040 permutations.

Upvotes: 6

Rubens Farias
Rubens Farias

Reputation: 57956

A pandigital number doesn't needs to contain all numbers from 1 to 9, but all from 1 to length.

So, you'll need to try all permutations from 1 to 9 starting with 1 digit and going up, filtering all prime numbers and, then, taking largest one.

Upvotes: 9

Related Questions