UVA - 343 - What Base Is This?

This article will explain my thought process to solve a problem called What Base Is This? (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Number Base, Base Conversion

Objective

Given:

A pair of numbers with an unknown base.

We want to:

Find the smallest pair of bases that produce an equal values.

Glossary

Number Base — The number of digits or combination of digits that a system uses to represent numbers.
Base Conversion — The process of expressing a numeral represented in one positional number system as an equivalent numeral in a different positional number system, preserving the quantity's value.

Observation

We have 36 possible digits from 0-9 and A-Z, which produce 35 possible number bases between 2 and 36. Since the number of bases is quiet small, we can try to parse the given number into every possible base to identify which pair of bases produce the identical values.

Since we want to find the smallest bases for the pair of numbers, we can sequentially convert the first number and the second number from the smallest to the largest possible base. The first iteration that produces an identical values is the answer.

Algorithm

For the base conversion, we can use Java’s built-in Long.parseLong(number, base) method to convert the number string into the desired base.

To explore every possible pair of bases, from the smallest to the largest pair, we can create a nested loop with the outer loop being the first base and the inner loop being the second base. Each loop will sequentially go from the smallest base (2) to the largest base (36).

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

Implementation

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

/**
 * 343 - What Base Is This?
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=279
 */
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();

        while (in.hasNext()) {
            final Input input = new Input();
            input.numberX = in.next();
            input.numberY = in.next();

            final Output output = process.process(input);
            if (output.hasMatches) {
                out.format("%s (base %d) = %s (base %d)\n", input.numberX, output.baseX, input.numberY, output.baseY);
            } else {
                out.format("%s is not equal to %s in any base 2..36\n", input.numberX, input.numberY);
            }
        }

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

class Input {
    public String numberX;
    public String numberY;
}

class Output {
    public boolean hasMatches;
    public int baseX;
    public int baseY;
}

class Process {
    private static final long INVALID = -1;

    public Output process(final Input input) {
        final Output output = new Output();
        output.hasMatches = false;

        for (int baseX = 2; baseX <= 36; baseX++) {
            final long valueX = parseLong(input.numberX, baseX);
            if (valueX == INVALID) continue;

            for (int baseY = 2; baseY <= 36; baseY++) {
                final long valueY = parseLong(input.numberY, baseY);
                if (valueY == INVALID) continue;

                final boolean matches = valueX == valueY;
                if (matches) {
                    output.hasMatches = true;
                    output.baseX = baseX;
                    output.baseY = baseY;
                    return output;
                }
            }
        }

        return output;
    }

    private long parseLong(final String number, final int base) {
        try {
            return Long.parseLong(number, base);
        } catch (NumberFormatException e) {
            return INVALID;
        }
    }
}