2
\$\begingroup\$

Project Euler Problem #4: Largest palindrome product:

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.

I got the correct answer for the problem, but I want to know if my coding style is good or bad for this solution.
I need to know how I can improve my coding, if it is bad and write this in a more general way.

#include<stdio.h>
#define MAX 999
#define START 100

int main()
{
   int i,j,current,n,prev = 0;
for(i = START;i<=MAX;i++)
{
    for(j=START;j<=MAX;j++)
    {
        current = j * i;
        if(current > prev)  /*check the current value so that if it is less need not go further*/
        {
            n = palindrome(current);
            if (n == 1)
            {
                printf("The palindrome number is : %d\n",current);
                prev = current;  // previous value is updated if this the best possible value.
            }
        }
    }
}
}

int palindrome(int num)
{
int a[6],temp;
temp = num;
/*We need a array to store each element*/
a[5] = temp % 10;       
a[4] = (temp/10) %10;
a[3] = (temp/100) %10;
a[2] = (temp/1000) %10;
a[1] = (temp/10000) %10;
if(temp/100000 == 0)
{
    a[0] = 0;
    if(a[1] == a[5] && a[2] == a[4])
        return 1;
}
else
{
    a[0] = (temp/100000) %10;
    if(a[0] == a[5] && a[1] == a[4] && a[2] == a[3])
        return 1;
    else
        return 0;
}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Please embed a short summary of the challenge in your question. \$\endgroup\$ – RubberDuck Oct 11 '15 at 11:25
  • 2
    \$\begingroup\$ @outoftime: The way I understand it, reformatting the code in questions asked about is explicitly something we don't do, as it renders part of possible reviews moot. \$\endgroup\$ – Deduplicator Oct 11 '15 at 14:50
  • \$\begingroup\$ @outoftime, It's probably easier to post the formatting changes as answer! \$\endgroup\$ – Quill Oct 11 '15 at 15:06
1
\$\begingroup\$
  1. First of all, you are only interested in the biggest number, so why do you start from the bottom??
    Correcting that allows you to dispense with an explicit lower boundary, a dynamic boundary can be computed depending on current-best result.
  2. Why don't you read the upper boundary from the command-line?
  3. Proper indentation is a very valuable help in quickly and accurately reading source-code, as well as ferreting out errors.
    In your case, the one level of indentation missing through much of your code might be an artifact of sloppy posting here. Whether or not it is, don't do that.
  4. You are depending on implicit definition of palindrome. Don't do that, reverse their positions.
  5. An int only has a guaranteed range of -32767 to 32767. Use a long (or unsigned long), that has the proper range without depending on implementation-dependent behaviour.
  6. Why do you use an array and all that paraphernalia to check for being a palindrome, simply reversing is easy:

    unsigned long reverse(unsigned long in) {
        unsigned long r = 0;
        for(; in; in /= 10)
            r = r * 10 + in % 10;
        return r;
    }
    

Final program (on coliru):

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

static int is_palindrome(const unsigned long in) {
    unsigned long r = 0;
    for(unsigned long x = in; x; x /= 10)
        r = r * 10 + x % 10;
    return r == in;
}

int main(int argc, char* argv[]) {
    unsigned long max = argc > 1 ? strtoul(argv[1], 0, 10) : 0;
    if(!max || max > 9999)
        max = 999;
    unsigned long _a = 0, _b = 0, _m = 0; // best yet
    for(unsigned long a = max, a_min = 1; a >= a_min; --a)
        for(unsigned long b = max, b_min = _m / a + 1; b >= b_min; --b)
            if(is_palindrome(a*b)) {
                _a = a, _b = b, _m = a*b, a_min = _m / max + 1;
                break;
            }
    printf("Biggest palindrome-number which is product of two natural numbers"
        " no bigger than %lu: %lu = %lu * %lu\n", max, _m, _a, _b);
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Thanks for the valuable help. I didn't think the idea of counting from the bottom. It will save lot of computing time thanks for the awesome info. \$\endgroup\$ – SUGMAR Oct 11 '15 at 15:34
  • \$\begingroup\$ Just be aware that while I can break the inner loop on finding a palindrome, I still cannot break the outer loop, only raise it's lower limit. \$\endgroup\$ – Deduplicator Oct 11 '15 at 15:37
  • \$\begingroup\$ Suggest if(!max || max > 9999) --> if(max > 999) (Change limit to 999). \$\endgroup\$ – chux Oct 12 '15 at 8:55
  • \$\begingroup\$ @chux: I set the limit to 9999 because all 4-digit-numbers can be squared and reversed in a long, but not all 5-digit-numbers. \$\endgroup\$ – Deduplicator Oct 12 '15 at 13:55
0
\$\begingroup\$

You could make your palindrome detecting function a little bit more general, so that it can handle any int, easily:

/* Range of int is -2,147,483,648 to 2,147,483,647 */
#define MAX_INT_DIGITS 10

int is_palindrome(int num)
{
    int idx;
    int count = 0;
    int digits[MAX_INT_DIGITS];

    while (num) {
        digits[count] = num % 10;
        num /= 10;
        ++count;
    }

    for (idx = 0; idx < count / 2; ++idx) {
        if (digits[idx] != digits[count - idx]) {
            return 0;
        }
    }

    return 1;
}

Notice especially how the magic number 10 (which would be 6 in your code), gets named for the code reader's benefit.

Also, since you are looking for the largest possible value, it is better to iterate from large to small values, and break out of loops early:

#define MAX_3_DIGIT 999
#define MIN_3_DIGIT 100

int main()
{
    int i, j;
    int largest_palindrome = 0;

    for (i = MAX_3_DIGIT; i >= MIN_3_DIGIT; --i) {
        if (MAX_3_DIGIT * i <= largest_palindrome) {
            break;
        }
        for (j = MAX_3_DIGIT; j >= MIN_3_DIGIT; --j) {
            int value = i * j;

            if (value <= largest_palindrome) {
                break;
            }
            if (is_palindrome(value)) {
                largest_palindrome = value;
                break;
            }
        }
    }
    return largest_palindrome;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Strictly speaking, your range of int is wrong. \$\endgroup\$ – Deduplicator Oct 11 '15 at 15:35
0
\$\begingroup\$

There is an easy way to check the digit palindrome without using array, but reverse the digit by using int instead

int isPalindrome(int n) {
    int np = 0;
    for(int r = n; r > 0; r /= 10) {
       np *= 10;
       np += r % 10; 
    }
    return n == np;
}

It is also better run from MAX down to START, because you can break immediately when you find first palindrome.

\$\endgroup\$
  • 1
    \$\begingroup\$ Breaking on finding the first palindrome is wrong. Still, the loop can be optimized severely by dynamically raising the lower bound when finding a new current-best solution. \$\endgroup\$ – Deduplicator Oct 11 '15 at 15:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.