Suppose you want to know how many palindromes are in the set of integers from 1 to N. Can you provide a formula for this? Otherwise, can you give an algorithm, as efficient as possible, to find the answer? And, are there special values of N for which there is a simple formula?

it's terribly written, but here is the C source code i wrote:

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

#define FALSE 0
#define TRUE 1

// returns the digit in the 10^k's place
int getDigit(int num, int place) {
    return (((num % (10 * place)) - (num % place)) / place);
}


// returns base^power
int power(int base, int power) {
    int answer = 1;
    for (int i = 0; i < power; i++) {
        answer *= base;
    }
    return answer;
}

//returns the number of digits in a number
int getNumDigits (int num) {
    int k = 0;
    while(1) {
        if ((num % power(10, k)) == num) {
            return k;
        }
        k++;
    }
    return -1;
}

// returns whether a number is a palindrome
int isPalindrome(int num) {
    int numDigits = getNumDigits(num);
    for (int i = 0; i <= (numDigits / 2); i++) {
        if (getDigit(num, power(10, i)) != getDigit(num, power(10, numDigits - 1 - i))) {
            return FALSE;
        }
    }
    return TRUE;
}

// return the next largest palindrome less than or equal to a number with the same length as that number
int nLP(int num) {
    int lp = num;
    int numDigits = getNumDigits(lp);
    if (isPalindrome(lp) == 1) {
        return lp;
    }
    if (getDigit(lp, pow(10, 0)) == 0) {
        return nLP(lp - 1);
    }
    for (int i = 0; i <= (numDigits / 2); i++) {
        lp -= (((getDigit(lp, power(10, i)) - getDigit(lp, power(10, numDigits - 1 - i))) + 10) % 10) * power(10, i);
        if (isPalindrome(lp) == 1) {
            return lp;
        }
    }
    return 0;
}


// returns the number of palindromes less than a number with the same number of digits as that number
// there are 6*6*3 = 108 palindromes less than 65346 that have 5 digits (biggest = 65256)
// there are 9*10*10 = 900 palindromes less than 999999 that have 6 digits
int numPalies(num) {
    int lp = nLP(num);
    int numDigits = getNumDigits(lp);
    int answer = 1;
    answer *= getDigit(lp, power(10, 0));
    for (int i = 1; i < (int)ceil((double)((double)numDigits / 2)); i++) {
        answer *= (getDigit(lp, power(10, i)) + 1);
    }
    return answer;
}


void main() {
    int num, numDigits;
    printf("Enter an integer: ");
    while (scanf("%d", &num) == 0) {
        printf("ERROR: Not An Integer\n");
        break;
    }
    numDigits = getNumDigits(nLP(num));
    printf("number of palindromes with %d digits less than or equal to %d is %d\n", numDigits, num, numPalies(num));
    for (int i = numDigits - 1; i > 0; i--) {
        printf("number of palindromes with %d digits less than or equal to %d is %d\n", i, power(10, i), numPalies(power(10, i) - 1));
    }
    int answer = numPalies(num);
    for (int i = numDigits - 1; i > 0; i--) {
        answer += numPalies(power(10, i) - 1);
    }
    printf("total number of palindromes less than or equal to %d is %d", num, answer);
}

Posted by cheesesteak on 2006-06-23 23:21:02