Optimizing Code for Project Euler Problem 04

Question

I just finished Problem 04 on Project Euler, and I was looking at ways to optimize my code, just started learning functions too, so I'm pretty sure it's very bad, hopefully you guys can help me.

Question

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 ×ばつ 99.

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

public class TestProblem10 {
 public static int checkPalindrome(int a, int b){
 boolean palindro = false;
 if (a % 1000000 / 100000 == a % 10 && a % 100000 / 10000 == a % 100 / 10 &&
 a % 10000 / 1000 == a % 1000 / 100) { // Checking if it's a palidrome
 if (a > b) { // Making sure to return the largest palindrome possible.
 b = a; // A = MULT B = PALINDROME
 palindro = true;
 }
 }
 if (palindro){
 return b;
 }else{
 return 0;
 }
 }

I do not like very much the 5th and the 6th line because it took so much space, if there's one way to make it better do let me know too please.

 public static void main(String[] args) {
 // var
 int palindrome = 0;
 // processing
 for (int i = 900; i < 1000; i++) {
 for (int k = 900; k < 1000; k++) {
 int mult = (i * k);
 if (checkPalindrome(mult, palindrome) == 0){
 continue; // Won't let the result = 0 when func returns 0
 }else{
 palindrome = checkPalindrome(mult, palindrome);
 }
 }
 }
 // out
 System.out.print("Largest palindrome made from the product of two 3-digit numbers is " + palindrome);
 }
}

Answer 1

Arithmetic simplification

if (a % 1000000 / 100000 == a % 10 && a % 100000 / 10000 == a % 100 / 10 &&
 a % 10000 / 1000 == a % 1000 / 100) {

An expression like a % 10...0 / 100 can be simplified to a / 100 % 10. So the whole condition becomes:

if (a / 100000 % 10 == a % 10 && a / 10000 % 10 == a / 10 % 10 &&
 a / 1000 % 10 == a / 100 % 10) {

Search range

for (int i = 900; i < 1000; i++) {
 for (int k = 900; k < 1000; k++) {

How do you know you'll find a palindromic product with i and k in the range [900, 1000); did you prove that?

How do you know that if you search i and k in the range [100, 1000), you won't find a bigger palindrome? (For example, pretend that ×ばつ900=810000 is the biggest palindrome in the first case but ×ばつ1000=899000 is the biggest palindrome in the second case.)

Absent a proof, the conservatively correct thing to do is to search the entire 3-digit range given by the problem:

for (int i = 100; i < 1000; i++) {
 for (int k = 100; k < 1000; k++) {

Extra parentheses

int mult = (i * k);

For this simple expression, it's clearer to not use parentheses:

int mult = i * k;

Common subexpression and control flow

if (checkPalindrome(mult, palindrome) == 0){
 continue; // Won't let the result = 0 when func returns 0
}else{
 palindrome = checkPalindrome(mult, palindrome);
}

Store the function result to avoid calling it twice, saving time and code:

int temp = checkPalindrome(mult, palindrome);
if (temp == 0){
 continue; // Won't let the result = 0 when func returns 0
}else{
 palindrome = temp;
}

Furthermore, change the if-continue to just a negative if:

int temp = checkPalindrome(mult, palindrome);
if (temp != 0){
 palindrome = temp;
}

Mixed concerns

Your function checkPalindrome() basically behaves like:

if (isPalindrome(a) && a > b)
 return b;
else
 return 0;

It's a weird function because it tests palindromes, figures out a maximum, or returns the special sentinel value of 0. I would advocate for writing a pure isPalindrome() Boolean function, and putting the maximum check in main() instead.

Access modifier

 public static int checkPalindrome(int a, int b){

The function doesn't need to be called from outside the class, so set it to private.

Full revised code

public class TestProblem10 {
 private static int checkPalindrome(int a, int b){
 boolean palindro = false;
 if (a / 100000 % 10 == a % 10 && a / 10000 % 10 == a % 100 / 10 &&
 a / 1000 % 10 == a / 100 % 10) { // Checking if it's a palidrome
 if (a > b) { // Making sure to return the largest palindrome possible.
 b = a; // A = MULT B = PALINDROME
 palindro = true;
 }
 }
 if (palindro){
 return b;
 }else{
 return 0;
 }
 }
 public static void main(String[] args) {
 // var
 int palindrome = 0;
 // processing
 for (int i = 100; i < 1000; i++) {
 for (int k = 100; k < 1000; k++) {
 int mult = i * k;
 int temp = checkPalindrome(mult, palindrome)
 if (temp != 0){
 palindrome = temp;
 }
 }
 }
 // out
 System.out.print("Largest palindrome made from the product of two 3-digit numbers is " + palindrome);
 }
}

My solution

Feel free to read my p004.java and Library.java. A preview:

int maxPalin = -1;
for (int i = 100; i < 1000; i++) {
 for (int j = 100; j < 1000; j++) {
 int prod = i * j;
 if (Library.isPalindrome(prod) && prod > maxPalin)
 maxPalin = prod;
 }
}
return Integer.toString(maxPalin);

• fabinfabinfabin: Thank you for sharing, also, why did you used Integer.toString ?
• Nayuki: I used Integer.toString() because it converts the number to a base-10 string, and it can handle any length palindrome. Your function checkPalindrome() only works correctly for 6-digit numbers. Actually, 100 × 100 = 10000 which is a 5-digit number, so there's a new bug in the program.