Mdthbs

Are there any efficient ways to solve this problem,
for example using bitwise operator?

    public static boolean isPal(long num) 

    {

        String numStr = Long.toString(num);

        String rNumStr = "";



        boolean result = false;



        for (int i = numStr.length() - 1; i >= 0 ; --i)

            rNumStr += numStr.charAt(i);



        //System.out.println(numStr + "," + rNumStr);

        try 

        {

            if (Long.parseLong(numStr) == Long.parseLong(rNumStr))

                result = true;

            else  

                result = false;

        }catch (NumberFormatException e) {

            //System.err.println("Unable to format. " + e);

        }

        return result;



    }



    public static void calcPal(int rangeMin, int rangeMax)

    {

        long maxp = 0, maxq = 0, maxP = 0;

        for (int p = rangeMax; p > rangeMin; p--)

            for (int q = rangeMax; q > rangeMin; q--)

            {

                long P = p * q;

                if (isPal(P))

                    if (P > maxP)

                    {

                        maxp = p; maxq = q; maxP = P;

                    }

            }

        System.out.println(maxp + "*" + maxq + "=" + maxP);

    }



    public static void main(String[] args) 

    {

        calcPal(10, 99);

        calcPal(100, 999);

        calcPal(9000, 9999);

        calcPal(10000, 99999);

        calcPal(990000, 999999);

    }

The largest palindrome which can be made from the product of two 2-digit (10 to 99) numbers is 9009 (91 × 99). Write a function to calculate the largest palindromic number from the product of two 6-digit numbers (100000 to 999999).

In an interview setting it is quite hard to come with an efficient solution (unless you happen to be very good in mental multiplication; however a $99 * 91$ example is a strong hint). The key to an efficient solution is an observation that

$999999 * 999001 = 999000000999$

is a quite large palindromic product. It means that you don't have to test the entire 6-digit ranges of multiplicands. It is enough to test multiplicands only in $[999001.. 999999]$ range. Just $10^6$ candidate pairs rather than $10^{12}$.

BTW, a similar identity holds for products of longer numbers as well.

Next, you may notice that there are just one thousand palindromic numbers larger than $999000000999$ (they are in form of 999abccba999), and to qualify as a solution is must have a 6-digit factor larger than $999001$. This implies the following algorithm (in pseudocode):

base = 999000000999

abc = 999

while abc >= 0

    cba = reverse_digits(abc)

    number = base + abc * 1000000 + cba * 1000

    for factor in 999001 to sqrt(number)

        if number % factor == 0:

           return number

    abc -= 1

The reverse_digits of a 3-digit number could be done extremely fast (a lookup table, for example). Still a $10^6$ or so rounds, but no expensive tests for palindromicity.

All that said, since the problem stems from Project Euler #4 it is possible that it admits a more elegant number-theoretical solution.

Bug

    for (int p = rangeMax; p > rangeMin; p--)

        for (int q = rangeMax; q > rangeMin; q--)

You are not including rangeMin in either of the loops, so you will never test products which involve the lower limit. You want >= in the loop condition:

    for (int p = rangeMax; p >= rangeMin; p--)

        for (int q = rangeMax; q >= rangeMin; q--)

Commutivity

Note that p * q == q * p, so you don't need to test all combinations in the range:

    for (int p = rangeMax; p > rangeMin; p--)

        for (int q = rangeMax; q > rangeMin; q--)

Only the ones where either p >= q or q >= p, which will reduce your search space by close to 50%! For example, you could change the q range to start at the current p value and go down from there:

    for (int p = rangeMax; p >= rangeMin; p--)

        for (int q = p; q >= rangeMin; q--)

Test order: Fastest tests first!

isPal(P) is an involved function which will take a bit of time. In comparison, P > maxP is blazingly fast. So instead of:

            if (isPal(P))

                if (P > maxP)

                {

                    maxp = p; maxq = q; maxP = P;

                }

how about:

            if (P > maxP)

                if (isPal(P))

                {

                    maxp = p; maxq = q; maxP = P;

                }

Early termination

If p*q is ever less than maxP, then multiplying p by any smaller value of q is a waste of time; you can break out of the inner loop, and try the next value of p.

If p*p is ever less than maxP, and the inner loop only multiplies p by q values which a not greater than p, then you can break out of the outer loop, too!

String Manipulation

The following is inefficient, because temporary objects are being created and destroyed during each iteration.

    for (int i = numStr.length() - 1; i >= 0 ; --i)

        rNumStr += numStr.charAt(i);

It is much better to use a StringBuilder to build up strings character by character, because the StringBuilder maintains a mutable buffer for the interm results.

Even better, it includes the .reverse() method, which does what you need in one function call.

StringBuilder sb = new StringBuilder(numStr);

String rNumStr = sb.reverse().toString();

Unnecessary Operations

Why convert numStr to a number using Long.parseLong(numStr)? Isn't the result simply num, the value that was passed in to the function?

Why convert rNumStr to a number? If num is a palindrome, then aren't numStr and rNumStr equal?

public static boolean isPal(long num) 

{

    String numStr = Long.toString(num);

    StringBuilder sb = new StringBuilder(numStr);

    String rNumStr = sb.reverse().toString();



    return numStr.equals(rNumStr);

}