Posts Tagged ‘palindrome’

I’m actually working out the problems proposed in Project Euler’s website and I thought that it could be useful for many people if I post here my solutions for some of them. 

The problem 4 says: 

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 x 99.

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

I just generalized this problem by writing out a modular program, in C, that finds the largest Palindrome for any number of digits given in the command line.

The program may seem larger than necessary, but that’s because I used some general functions I defined a while ago for other purposes, so they work fine with any (valid) input (so at the far end that made me easier to structure the program 🙂 ).

#include <stdio.h>
#include <stdlib.h>
 
double exponenciar (double base, int exponent); 
/* Returns the result of (base ^ exponent) */
 
int calculaXifres (int n);
/* Returns the number of digits of the number "n". */
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud); 
/* Maps each element of the array of integers
 "array_de_integers", of "longitud" elements, 
to each digit of an integer, and returns it back. 
For instance,
 
aIntegerstoInteger ({2, 1, 5}, 3) 
 
will return 215. I will only use this function once, 
just for making easier the inversion of a number. */
 
long int invertirNumero (long int num); 
/* Returns the number "num" inverted */
 
long int maxValueNdigits (int num_digits); 
/* Returns the maximum value that a number with 
"num_digits" digits can reach. For example, 
maxValueNdigits (4) would return 9999. */
 
long int largestPalindrome (int num_digits); 
/* Returns the answer of this problem when 
num_digits = 3. */
 
 
double exponenciar (double base, int exponent){
 
    double retorna;
 
    if (exponent == 0){
      retorna = 1;
    } else {
      retorna = base * exponenciar (base, exponent - 1);
    }
 
    return retorna;
}
 
int calculaXifres (int n){
 
    int quocient = n;
    int comptador = 0;
 
    while (quocient > 0){
      quocient = quocient / 10;
      comptador++;
    }
 
    return comptador;
}
 
long int aIntegerstoInteger (long int array_de_integers[], 
                             int longitud){
     
    int num_elements = longitud;
    int i = 0;
    long int integer = 0;
 
    for (i = 0; i < num_elements; i++){
      integer += array_de_integers[i] * 
                 (int) exponenciar (10, num_elements - (i + 1));
    }
 
    return integer;
}
 
long int invertirNumero (long int num){
     
    int longitud = calculaXifres (num);
    long int num_invertit[longitud];
    long int numero_invertit;
    int i = 0;
     
    for (i = 0; i < longitud; i++){
      num_invertit[i] = num % 10;
      num = num / 10;
    }
 
    numero_invertit = aIntegerstoInteger (num_invertit, longitud);
 
    return numero_invertit;
}
 
 
long int maxValueNdigits (int num_digits){
     
    int i = 0;
    long int max_value = 0;
 
    for (i = 0; i < num_digits; i++){
       max_value = max_value + (int) exponenciar (10, i);
    }
 
    max_value = 9*max_value;
 
    return max_value;
}
 
 
long int largestPalindrome (int num_digits){
     
    long int starting = (long int) exponenciar (10, num_digits - 1);
    long int ending = maxValueNdigits(num_digits);
    long int i = starting;
    long int j = i;
    long int largest_palindrome = 0L;
 
    for (i = starting; i <= ending; i++){
      for (j = starting; j <= ending; j++){
         if (i * j == invertirNumero (i * j) &&
            i * j >= largest_palindrome){
            largest_palindrome = i * j;
         }
      }
    }
 
    return largest_palindrome;
}
 
 
int main (int argc, char *argv[]){
 
    int num_digits = atoi (argv[1]);
 
    printf ("%ld\n", largestPalindrome (num_digits));
     
    return 0;
}

Time to compile and to execute the program:

$ (gcc -Wall -Wconversion prob4.c) && ./a.out 3
906609

And the three-digit factors are 993 and 913, it is to say, 993 \times 913 = 906609.

Advertisements