Project Euler Solution 4

Problem Statement

Find the largest palindrome made from the product of two 3-digit numbers.

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.

Solution

• A palindrome number never ends with zero. So the product of two numbers is not a palindrome if one or both of the numbers involved in the product is a multiple of 10.
• After finding the product of two numbers check if the product is greater than the palindrome number found so far.
• Finding palindrome number : For example 956659 is a palindrome number

The following table shows the position of each digits in an array

index	0	1	2	3	4	5
Digits	9	5	6	6	5	9

Initially i=0 and m=5

index	i = 0	1	2	3	4	j = 5
Digits	9	5	6	6	5	9

Digits match so increment i by 1 and decrement j by 1.

i = 1, j = 4

index	0	i = 1	2	3	j = 4	5
Digits	9	5	6	6	5	9

Digits match so increment i by 1 and decrement j by 1.

i = 2, j = 3

index	0	1	i = 2	j = 3	4	5
Digits	9	5	6	6	5	9

Digits match so increment i by 1 and decrement j by 1

i = 3, j = 2

i > j. This is the terminating condition

note

If the number of digits in the number is odd, the terminating condition is i == j. So generalizing it if the number is a palindrome then the terminating condition is i >= j.

Implementation

#include <iostream>
using namespace std;
int main(){    int num1, num2, product, t_prod, i, j;    int no_digits, larg_palindrome;    int prod_array[10];
    product = 1;    no_digits = 0;    larg_palindrome = 1;
    for (num1 = 100; num1 < 1000; num1++)    {        if (num1 % 10 == 0) continue;        for (num2 = 100; num2 < 1000; num2++)        {            if (num2 % 10 == 0) continue;            no_digits = 0;            product = num1 * num2;            t_prod = product;            if (product > larg_palindrome)            {                while (t_prod > 0)                {                    prod_array[no_digits] = t_prod % 10;                    no_digits++;                    t_prod = t_prod / 10;                }                i = 0;                j = no_digits - 1;                while (prod_array[i] == prod_array[j])                {                    i++;                    j--;                    if (i >= j)                    {                        larg_palindrome = product;                        break;                    }                }            }        }    }    cout << larg_palindrome;    return 0;}

Sample Output