2
\$\begingroup\$

The following code is a C solution to the following problem UVA 10018.

The Problem

The "reverse and add" method is simple: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure.

For example:

195 Initial number
591

786
687

1473
3741

5214
4125

9339 Resulting palindrome

In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.

Task

You must write a program that give the resulting palindrome and the number of iterations (additions) to compute the palindrome.

You might assume that all tests data on this problem:

  • will have an answer
  • will be computable with less than 1000 iterations (additions)
  • will yield a palindrome that is not greater than 4,294,967,295.

The Input

The first line will have a number N with the number of test cases, the next N lines will have a number P to compute its palindrome.

The Output

For each of the N tests you will have to write a line with the following data : minimum number of iterations (additions) to get to the palindrome and the resulting palindrome itself separated by one space.

Sample Input

3
195
265
750

Sample Output

4 9339
5 45254
3 6666

My solution is as follows:

#include <stdio.h>

/* only works for unsigned longs */
unsigned long reverse(unsigned long original)
{
  unsigned long number = original;
  unsigned long reversed = 0;
  unsigned long place = 1;
  unsigned long i, q;

  for(i = 1000000000; i > 0; i = i / 10) {

    q = number / i;

    if ((q > 0) || (reversed > 0)) {
      reversed = reversed + (q * place);
      number = number - (q * i);
      place = place * 10;
    }
  }

  return(reversed);
}

int is_palindrome(unsigned long original)
{
  unsigned long reversed;
  reversed = reverse(original);
  return(reversed == original);
}

unsigned long reverse_add(unsigned long original, int *iterations)
{
  if (is_palindrome(original)) {
    return(original);
  }

  if (*iterations >= 1000) {
    return(0);
  }

  *iterations = *iterations + 1;
  reverse_add(original + reverse(original), iterations);
}

int main()
{
  int n = 0;
  unsigned long start;
  unsigned long end;
  int iterations = 0;

  while (scanf("%ld\n", &start) == 1) {
    if (n == 0) {
      n = start;
    }
    else {
      iterations = 0;
      end = reverse_add(start, &iterations);
      printf("%d %ld\n", iterations, end);
    }
  }

  return(0);
}
\$\endgroup\$
5
\$\begingroup\$

reverse()

Your reverse() function only works for numbers below 1010. Although that upper bound may be good enough to solve this particular challenge, it's not correct in general. (Keep in mind that the standard says that an unsigned long is at least 32 bits — possibly larger.)

Here is a simpler implementation that works in general:

unsigned long reverse(unsigned long original) {
    unsigned long reversed = 0;
    for (; original; original /= 10) {
        reversed = (10 * reversed) + (original % 10);
    }
    return reversed;
}

is_palindrome()

For every iteration, you end up calling reverse() twice: once to test whether a palindrome has appeared, and again to obtain the next number to add. You would be better off eliminating this function, and rolling the palindrome check into the reverse_add() loop itself.

reverse_add()

For clarity, I would rename the function to reverse_add_until_paindrome().

Conventionally, C functions are designed so that a status code is returned, and the data being manipulated are passed by reference. I recommend redesigning the interface so that it returns the number of iterations, as that is closer in spirit to a status code. The number itself can be passed by reference. Notice what happens then: it becomes an in-out parameter! The rationale for the convention makes itself apparent.

int reverse_add_until_palindrome(unsigned long *n) {
    int i;
    unsigned long rev;
    for (i = 0; (rev = reverse(*n)) != *n; i++) {
        *n += rev;
    }
    return i;
}

The problem statement guarantees that you will never be given a P that will require more than 1000 iterations. That's just for your information; I don't think you need to verify that fact. (If you do want to bail out, you should add code in main() to detect that the computation was aborted.)

main()

The way you try to use one scanf() to read both N and the Pi is awkward. Not only does that make the code less clear, it also imposes a penalty of an extra conditional on every subsequent loop. In addition, it's wrong: the format string for an int is "%d", whereas the format string for an unsigned long is "%lu".

You read n, but never make use of it. That works, I suppose. I prefer to use it to see whether all of the expected input was received.

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

int main() {
    int n;
    unsigned long p;

    if (1 != scanf("%d", &n)) {
        return EXIT_FAILURE;
    }
    while (n-- && scanf("%lu", &p)) {
        int iterations = reverse_add_until_palindrome(&p);
        printf("%d %lu\n", iterations, p);
    }
    return (n == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}
\$\endgroup\$
1
\$\begingroup\$

Missing return

This line:

reverse_add(original + reverse(original), iterations);

should be:

return reverse_add(original + reverse(original), iterations);

If the program is working as is, you must be getting lucky.

\$\endgroup\$
0
\$\begingroup\$

It looks good overall. Nice short functions. Variable names are clear and easy to follow.

  while (scanf("%ld\n", &start) == 1) {

This will require you to hit enter twice to get the data in there. Better would be to add a space character at the front of the format string. This instructs scanf to eat any whitespace in front of the number.

On the other hand, if you're strictly reading from a file, then this code is fine.

  if (*iterations >= 1000) {
    return(0);
  }

I think it would be more interesting to actually return end in this case as well. You will be able to see that it is not a palindrome (and the rules don't forbid this), and it would be interesting to see what happens when it hits that rule. It is important to have a bound so you don't hit the undefined behavior of arithmetic overflow.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.