CODEWITHSUNDEEP
javaalgorithmpalindrome
James K J
James K J

Reputation: 615

Improved solution of problem 4 from Project euler

I have come across many many solutions in StackOverflow for problem 4 in project Euler. My question is not about asking again a solution to problem 4 from project Euler which is already implemented in StackOverflow. Instead, i have come across an improved solution Improved solution by ROMANIA_engineer. I have two questions against the improved solution. Anyways I have posted the solution below, for people to look into it.

public static void main(String[] args) {

int max = -1;

for ( int i = 999 ; i >= 100 ; i--) {
    if ( max >= i*999 ) { 
        break;
    }
    for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
}       
System.out.println(max > -1? max : "No palindrome found");
}

Questions

  1. Why there is a condition (max >= i * 999) ?. What are we going to achieve, by including such an inexpensive operation?

From the below snippet, 

for (int j = 999 ; j >= i ; j-- ) {             
        int p = i * j;
        if ( max < p && isPalindrome(p) ) {
            max = p;
        }
    }
  1. Instead of j >= 100, it is given j >= i. I can see a lot of time is saved, however, I wanted to know the intention behind it.

Upvotes: 0

Views: 586

Answers (1)

Chris Gong
Chris Gong

Reputation: 8229

To answer question 1, the reason why there is a check (max >= i * 999) is that you may have already stumbled upon a product of two 3-digit numbers that is a palindrome but greater than i * 999. Since the outer for loop starts at i = 999, once you've found a new max, there is a possibility that the new max is greater than the max possible palindrome product from the decremented i value in the next iteration. For example, if we found a palindrome product of 926 * 998 where i = 926 and j = 998 and the new max was set to this product. Note that this is just a hypothetical, I have no idea if the product is even a palindrome. Then the inner for loop finishes on the iteration i = 926. Then on the next iteration of the outer for loop, i is now 925, and since 925 * 999 is less than 926 * 998, there's no need to continue finding the max palindrome product because it's already been found. The reason is that at this point 925 * 999 is the largest possible palindrome product that can be calculated going forward.

To answer question 2, the reason for j >= i is to avoid repeating the calculation of products. For example, let's say the condition was j >= 100 instead. On the first iteration of the inner for loop when j is 999 and i is also 999. We will end up calculating, possibly, products from 999 * 999, 999 * 998, all the way to 999 * 100. However, if the inner for loop is ever reached to a point where i is now 100 and j is 999, then you'll ultimately repeat the calculation 100 * 999. Note that this is just an example, it may not even get to this point.

Upvotes: 1

Related Questions