Home > Blockchain >  Project Euler #4 largest palindrome (Java)
Project Euler #4 largest palindrome (Java)

Time:10-18

Problem : Find the largest palindrome made from the product of two 3-digit numbers.

public class Problem4 {

    public static void main(String[] args) {
        System.out.print(largestPalindrome());
    }
    
    static String largestPalindrome () {
        String s = "";
        for (int j = 999; j > 99; j--) {
            for (int k = 999; k > 99; k--) {
                s = String.valueOf(j*k);
                if (palindrome(s)) {
                    return s;
                }
            }
        }
        return s;
    }
    
    static boolean palindrome (String s) {
        for(int i = 0; i <= (s.length() / 2); i  ) {
            if (s.charAt(i) != s.charAt(s.length()-i-1)) {
                return false;
            }
        }
        return true;
    }
}

The correct answer would be 906609, I guess. But I keep getting 580085. Can someone tell me, what's wrong with my code? Thank you ☺️

CodePudding user response:

You return to early, i.e after finding the first palindrome regardless if it is the largest or not. The factors of the two palindroms you provided are

1 × 580085 = 580,085
5 × 116017 = 580,085
11 × 52735 = 580,085
53 × 10945 = 580,085
55 × 10547 = 580,085
199 × 2915 = 580,085
265 × 2189 = 580,085
583 × 995  = 580,085



1 × 906609 = 906,609
3 × 302203 = 906,609
11 × 82419 = 906,609
33 × 27473 = 906,609
83 × 10923 = 906,609
249 × 3641 = 906,609
331 × 2739 = 906,609
913 × 993  = 906,609

Looking at the products formed from two three digit numbers 995 x 583 is calculated before 993 x 913. A simple solution could be to introduce a variable as a holder for max value and an additional check for each palindrom if it is the largest value found and return first after checking all possible values.

static String largestPalindrome () {
    int max = Integer.MIN_VALUE;
    String s = "";
    for (int j = 999; j > 99; j--) {
        for (int k = 999; k > 99; k--) {
            s = String.valueOf(j*k);
            if (palindrome(s)) {
                if (j*k > max){
                    max = j*k;
                }
            }
        }
    }
    return String.valueOf(max);
}
  •  Tags:  
  • java
  • Related