Number palindrome function doesn't return largest palindrome

Question

I'm trying to make a function that finds the largest palindrome made of 3-digit factors. When I run the code, it finds a palindrome, but it's not the largest. Don't criticize my code, especially the goto, as I'm pretty new to C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(int number) {
    int palindrome = 1;
    char *str = (char *)malloc(8 * sizeof(char));
    sprintf(str, "%d", number);
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        if ((str[i] == str[len - (i+1)]) && palindrome) continue;
        else palindrome = 0;
    }
    free(str);
    return palindrome;
}

int main(void) {
    char* omg = "\xF0\x9F\x98\xB2";
    int factorI = 0;
    int factorJ = 0;
    for (int i = 999; i >= 100; i--) {
        for (int j = 999; j >= 100; j--) {
            if (isPalindrome(i * j)) {
                factorI = i;
                factorJ = j;
                goto end_loop;
            }
        }
    }
    end_loop: printf("Done! Found palindrome. (%s%s%s)\n", omg, omg, omg);
    printf("i: %d\nj: %d\n", factorI, factorJ);
    printf("PALINDROME: %d", factorI * factorJ);
    printf("\n\nHello World\n");
    return 0;
}

When I run the code, I get this:

Done! Found palindrome. (😲😲😲)
i: 995
j: 583
PALINDROME: 580085

Hello World

But that doesn't seem to be the biggest palindrome, because when I enter it into Project Euler, it marks the solution as incorrect. Can anyone help debug my code and see where I messed up? I looked over it like three times and I found nothing. PLEASE don't tell me the correct factors/palindrome, just help me with my code.

Answer 1

Your algorithm is faulty. For each number from 999 to 100 it then loops from 999 to 100 and checks for the first palindromic number. But this is not the largest such number.

That is 906609 and is formed by 913 and 993. Your algorithm never reaches this combination because it found a combo of 995 and a much smaller number first.

You can use your loops, but you need to continue looping and compare to a maximum. We'll start by setting this to 0.

int main(void) {
    int factorI = 0;
    int factorJ = 0;
    int max = 0;
    for (int i = 999; i >= 100; i--) {
        for (int j = 999; j >= 100; j--) {
            int ij = i * j;
            if (isPalindrome(ij) && ij > max) {
                factorI = i;
                factorJ = j;
                max = ij;
            }
        }
    }
    printf("Done! Found palindrome.\n");
    printf("i: %d\nj: %d\n", factorI, factorJ);
    printf("PALINDROME: %d\n", max);

    return 0;
}

We can optimize a bit by not checking duplicates. If we've checked 999, 995, there's no reason to check 995, 999.

    for (int i = 999; i >= 100; i--) {
        for (int j = i; j >= 100; j--) {
            int ij = i * j;
            if (isPalindrome(ij) && ij > max) {
                factorI = i;
                factorJ = j;
                max = ij;
            }
        }
    }

Optimizing further

We can realize that if we find a matching three digit j for a given value of i, if we try a smaller value of i, we're not going to get a bigger product with a smaller value of j. So we need to dynamically set the lower bound for j.

int main(void) {
    int factorI = 0;
    int factorJ = 0;
    int max = 0;

    int min_j = 100;

    for (int i = 999; i >= 100; i--) {
        for (int j = i; j >= min_j; j--) {
            int ij = i * j;
            if (isPalindrome(ij) && ij > max) {
                factorI = i;
                factorJ = j;
                max = ij;
                min_j = j;
                
                break;
            }
        }
    }
    printf("Done! Found palindrome.\n");
    printf("i: %d\nj: %d\n", factorI, factorJ);
    printf("PALINDROME: %d\n", max);

    return 0;
}

For three digit numbers this means that for i = 999, 998, 997, 996 we'll have to test all the way down to 100. But, on i = 995 we'll find a match at j = 583. We'll note that this is the largest palidrome found so far with factors 995 and 583 and break the inner loop. Now for i = 994, 993 we're only looping j down to 583 rather than needlessly to 100. For i = 993 we find a match at 913. This means that for the remaining loops we iterate j from:

992 -> 913
991 -> 913
990 -> 913
989 -> 913
988 -> 913
...
914 -> 913
913 -> 913
912 -> 913

Oh, look at that, all of the remaining iterations of i do nothing.

The isPalindrome function

This works with your existing isPalindrome, but that can be greatly improved by removing the dynamic memory allocation, only looping halfway over the string, and cleaning up the control flow in your loop.

int isPalindrome(int number) {
    char str[32];
    sprintf(str, "%d", number);
    size_t len = strlen(str);
    
    for (size_t i = 0; i < len / 2; i++) {
        if (str[i] != str[len - (i+1)]) 
            return 0; 
    }
    
    return 1;
}