c - find palindrome

Question

I'm a newcomer to programming, and I chose C as my first language(been learning it for a month or so). I've been trying to solve this palindrome question for hours and still couldn't come up with a satisfying solution. The question is here (from SPOJ), and here's my code:

#include <stdio.h>
#include <string.h>
void plus_one(char *number);
int main(void)
{
    char number[1000001];
    int i, j, m, k, indicator;
    int a;
    scanf("%d", &j);
    for (i = 0; i < j; i++) {
        scanf("%s", number);
        k = 1;
        while (k != 0) {
            plus_one(number);
            a = strlen(number);
            indicator = 1;
            for (m = 0; m < a / 2; m++) {
                if (number[m] != number[a - m - 1]) {
                    indicator = 0;
                    break;
                }
            }
            if (indicator != 0) {
                printf("%s\n", number);
                k = 0;
            }
        }
    }
    return 0;
}

void plus_one(char *number)
{
    int a = strlen(number);
    int i;
    number[a - 1]++;
    for (i = a; i >= 0; i--){
        if (number[i - 1] == ':') {
            number[i - 1] = '0';
            number[i - 2]++;
        }
        else
            break;
    }
    if (number[0] == '0') {
        number[0] = '1';
        strcat(number, "0");
    }
    return;
}

My idea was to examine every number greater than the input until a palindrome is found, and it worked well on my computer. But SPOJ responded "time limit exceeded", so I guess I need to find the next palindrome possible myself instead of using brute force. Can someone please give me a hint about how I can make this go faster? Thanks!

Answer 1

Since you're asking for a hint and not for C code (which I'm notoriously bad at), here's what I would do:

1. Determine if the number k has an even or odd number of digits, store that in a boolean called odd.
2. Take the first half of the number k, including the middle digit if odd is true, and store it in a variable called half.
   808 -> 80
2133 -> 21
3. Mirror the half variable, taking care to not duplicate the middle digit if odd is true, and store it in a variable called mirror.
   80 -> 808
21 -> 2112
4. Check if mirror > k
   • If true: you found your result
   • If false: increment half and start over from step 3.
     (After maximum one increment you're guaranteed to have found your result.)
     80 -> 81 -> 818
21 -> 22 -> 2222

---

Here's a JavaScript implementation for your reference:

const palin = (k) => {
  const mirror = (half, odd) => half + Array.from(half).reverse().join('').substring(odd);
  
  const s = k.toString();
  const odd = s.length % 2;
  const half = s.substring(0, Math.floor(s.length / 2) + odd);
  
  let mirrored = mirror(half, odd);
  
  if (+mirrored <= k) {
    mirrored = mirror((+half + 1).toString(), odd);
  }
  
  return mirrored;
}

console.log(palin(5));
console.log(palin(808));
console.log(palin(2133));