Why will this java string routine not print the answer?

Question

I have been working on the Project Euler problem 4. I am new to java, and believe I have found the answer (906609 = 993 * 913, by using Excel!).

When I print the line commented out, I can that my string manipulations have worked. I've researched a few ways to compare strings in case I had not understoof something, but this routine doesn't give me a result.

Please help me identify why it is not printing the answer?

James

public class pall{
    public static void main(String[] args){

    int i;
    int j;
    long k;
    String stringProd;

    for(i=994;i>992; i--){
        for (j=914;j>912; j--){
            k=(i*j);
            stringProd=String.valueOf(k);
            int len=stringProd.length();

            char[] forwards=new char[len];
            char[] back = new char[len];

            for(int l=0; l<len; l++){
                forwards[l]=stringProd.charAt(l);
            }

            for(int m=0; m<len;m++){
                back[m]=forwards[len-1-m];

            } 

            //System.out.println(forwards);
            //System.out.println(back);

            if(forwards.toString().equals(back.toString())){
                System.out.println(k);}
            }
        }
    }
}

Take a look here -> http://stackoverflow.com/questions/3442090/java-what-is-this-ljava-lang-object — blgt, Sep 24 '13 at 11:06

Rohit Jain · Accepted Answer · 2013-09-24T11:24:12.007

You are comparing the string representation of your array. toString() doesn't give you what you think. For example, the below code makes it clear:

char[] arr1 = {'a', 'b'};
char[] arr2 = {'a', 'b'};

System.out.println(arr1.toString() + " : " + arr2.toString());

this code prints:

[C@16f0472 : [C@18d107f

So, the string representation of both the arrays are different, even though the contents are equal. This is because arrays don't override toString() method. It inherits the Object#toString() method.

The toString method for class Object returns a string consisting of the name of the class of which the object is an instance, the at-sign character @, and the unsigned hexadecimal representation of the hash code of the object. In other words, this method returns a string equal to the value of:
getClass().getName() + '@' + Integer.toHexString(hashCode())

So, in the above output, [C is the output of char[].class.getName(), and 18d107f is the hashcode.

You can't also compare the arrays using forward.equals(back), as arrays in Java don't override equals() or hashCode() either. Any options? Yes, for comparing arrays you can use Arrays#equals(char[], char[]) method:

if (Arrays.equals(forward, back)) {
    System.out.println(k);
}

Also, to get your char arrays, you don't need those loops. You can use String#toCharArray() method. And also to get the reverse of the String, you can wrap the string in a StringBuilder instance, and use it's reverse() method:

char[] forwards = stringProd.toCharArray();
char[] back = new StringBuilder(stringPod).reverse().toString().toCharArray();

And now that you have found out an easy way to reverse a string, then how about using String#equals() method directly, and resist creating those character arrays?

String stringPod = String.valueOf(k);
String reverseStringPod = new StringBuilder(stringPod).reverse().toString()

if (stringPod.equals(reverseStringPod)) {
    System.out.println(k);
}

Finally, since it is about project euler, which is about speed and mostly mathematics. You should consider avoiding String utilities, and do it with general division and modulus arithmetic, to get each individual digits, from beginning and end, and compare them.

Thank you very much for taking the time to explain this - it's been a useful insight into how strings work and has helped me get under the hood of what's going on (the example at the start was particularly useful!). I will be using your advice re: stringbuilder in the future. — James Griffiths, Sep 24 '13 at 11:49
@JamesGriffiths: Though `StringBuilder` can of course be used. You should try your hand on this problem without using String API. For all the project euler problem, you can solve them with and without API, and then compare the performance. — Rohit Jain, Sep 24 '13 at 11:50

score 2 · Answer 2 · edited Sep 24 '13 at 11:25

To convert a string to char[] use

char[] forward = stringProd.toCharArray();

To convert a char[] to String, use String(char[]) constructor:

String backStr = new String(back); // Not the same as back.toString()

However, this is not the most performant solution, for several reasons:

You do not need to construct a back array to check if a string is a palindrome - you can walk the string from both ends, comparing the characters as you go, until you either find a difference or your indexes meet in the middle.
Rather than constructing a new array in a loop, you could reuse the same array - in case you do want to continue with an array, you could allocate it once for the maximum length of the product k, and use it in all iterations of your loop.
You do not need to convert a number to string in order to check if it is a palindrome - you can get its digits by repeatedly taking the remainder of division by ten, and then dividing by ten to go to the next digit.

Here is an illustration of the last point:

boolean isPalindrome(int n) {
    int[] digits = new int[10];
    if (n < 0) n = -n;
    int len = 0;
    while (n != 0) {
        digits[len++] = n % 10;
        n /= 10;
    }
    // Start two indexes from the opposite sides
    int left = 0, right = len-1;
    // Loop until they meet in the middle
    while (left < right) {
        if (digits[left++] != digits[right--]) {
            return false;
        }
    }
    return true;
}

A concise answer to the problem, thank you. There's some efficiencies here, and a numerical approach which I hadn't considered. — James Griffiths, Sep 24 '13 at 11:50

Why will this java string routine not print the answer?

2 Answers2