Why my C code gives incorrect output for next palindrome

Question

I have a C code(find next smallest palindrome), which when I run in my local Mac(osx: 10.11.4) and in ideone, it gives wrong result for the same input. It does not give wrong for all the inputs but for some of the inputs.

For example here is ran by ideone: http://ideone.com/T4tqak

Here are my results for same input:

input in local:

8
97795375756122352572879826552151654387112262
1892388497169516734992356528466
19891859448286167812
47737795782241879811566697829238862994263278849942632926438725
857751275744476297149515661
699
5119783738665448121162642286
4177118624313412937235746451

output in local:

97795375756122352572877827525322165757359779
1892388497169516159617948832981
19891859444495819891
47737795782241879811566697829233292879666511897814228759773774
857751275744474447572157758
707
5119783738665445668373879115
4177118624313443134268117714

Here is the C code for reference:

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

int all_nine(char* input){
  int result = 1, i;
  for(i = 0; i < strlen(input); ++i){
    if(input[i] != '9')
      return 0;
  }
  return result;
}

char* increase_one(char* input){
  int i;
  for(i = strlen(input) - 1; i >= 0; --i) {
    if(input[i] < '9'){
      input[i] += 1;
      break;
    }
    else{
      input[i] = '0';
    }
  }
  return input;
}


char* increase_make_palin(char* input){
  int input_len = strlen(input);
  int half_len = input_len%2 ? input_len/2 : input_len/2 - 1;
  int carry = 1, i;
  for(i = half_len; i >= 0; --i) {
    int cur_val = input[i] - '0';
    carry = (cur_val + carry) / 10;
    int new_val = (cur_val + carry) % 10;
    input[i] = input[input_len - 1 - i] = '0' + new_val;
  }
  return input;
}
char* next_palin_for_me(char* input){
    int input_len = strlen(input);
    int half_len = input_len/2  - 1, i;
    for(i = half_len; i >= 0; --i) {
      if(input[i] > input[input_len - 1 - i]){
        input[input_len - 1 - i] = input[i];
      } else {
        return increase_make_palin(input);
      }
    }
    return input;
}

char* next_palin(char* input){
  int input_len = strlen(input);
  if(all_nine(input)){
    return next_palin_for_me(increase_one(input));
  }
  if(input_len == 1){
    input[0] += 1;
    return input;
  }
  input = increase_one(input);
  return next_palin_for_me(input);
}

int main() {
  int n, i;
  scanf("%d", &n);
  char input[1000010];
  for(i = 0 ; i < n ; i++){
    scanf("%s", input);
    char* result = next_palin(input);
    printf("%s\n", result);
  }
  return 0;
}

Answer 1

The problem is here:

char* increase_make_palin(char* input){
    ...
    carry = (cur_val + carry) / 10;
    int new_val = (cur_val + carry) % 10;
    ...
}

Note that you change carry before you use it. Reverse the order of these two lines, and your code will work as you expect.

You can use 8799 as test input, to see how this works. You could have discovered this yourself, by stepping through with a debugger, or reducing your failure case to a simpler one.

As for why it gave the correct answer with the wrong code on ideone (if it actually did; I haven't tried it), I can only guess that perhaps the encoding of the numerals is different there, which would cause trouble with your "- '0'" approach.

Edit:

char* increase_make_palin(char* input){
  int input_len = strlen(input);
  int half_len = input_len%2 ? input_len/2 : input_len/2 - 1;
  int carry = 1, i = half_len;
  while(i > 0){
    if(input_len%2 == 0){
      if(input[i] == input[input_len - 1 - i]) {
        i--;
        continue;
      }
      if(input[i] > input[input_len - 1 - i]) {
        carry = 0;
        break;
      }
      else{
        break;
      }
    }
    if(input_len%2){
      if(input[i-1] == input[input_len - i]){
        i--;
        continue;
      }
      if(input[i-1] > input[input_len - i]){
        carry = 0;
        break;
      }
      else{
        break;
      }
    }
  }
  for(i = half_len; i >= 0; --i) {
    int cur_val = input[i] - '0';
    int new_val = (cur_val + carry) % 10;
    carry = (cur_val + carry) / 10;
    input[i] = input[input_len - 1 - i] = '0' + new_val;
  }
  return input;
}