UVA - 10018 - Reverse and Add

This article will explain my thought process to solve a problem called Reverse and Add (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Palindrome

Objective

Given:

A number.

We want to:

Find the palindrome number by repeating reverse-add operation.
Find the total iterations to reach palindrome number.

Glossary

Palindrome — A word, number, phrase, or other sequence of symbols that reads the same backwards as forwards.

Observation

We have 3 base operations: (1) reverse number, (2) add numbers, and (3) palindrome number check. For reverse number operation, we can reverse the number by rearranging the digits in backwards order. For palindrome number check, we just need to make sure that the reversed number is identical to the original number.

After we have defined the base operations, we need to repeat the reverse and add operations until we have a palindrome number. During each repetition, we need to keep track of the total iterations as well.

Algorithm

To implement the reverse number operation, for simplicity, we can convert it into string and reverse the string using java’s string builder class. To implement the palindrome number check, we can re-use the reverse number operation to compare the original number and the reversed number.

The time complexity of this solution is O({total iterations} * {total digits}) or O(10^4).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 10018 - Reverse and Add
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=959
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalCases = in.nextInt();
        for (int i = 0; i < totalCases; i++) {
            final Input input = new Input();
            input.number = in.nextLong();

            final Output output = process.process(input);
            out.format("%d %d\n", output.totalIterations, output.palindrome);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public long number;
}

class Output {
    public long totalIterations;
    public long palindrome;
}

class Process {
    public Output process(final Input input) {
        long totalIterations = 0, number = input.number;
        while (!isPalindrome(number)) {
            totalIterations++;
            number += reverse(number);
        }

        final Output output = new Output();
        output.totalIterations = totalIterations;
        output.palindrome = number;
        return output;
    }

    private boolean isPalindrome(final long number) {
        return number == reverse(number);
    }

    private long reverse(final long number) {
        final String text = Long.toString(number);
        final String reverseText = reverse(text);
        return Long.parseLong(reverseText);
    }

    private String reverse(final String text) {
        return new StringBuilder(text).reverse().toString();
    }
}