Numbers have different representations depending on the bases on which they are expressed. For example, in base 3, the number 12 is written as 110 (1 x 3² + 1 x 3¹ + 0 x 3⁰) but base 8 it is written as 14 (1 x 8¹ + 4 x 8⁰).

Consider for example, the integers 12 and 5. Certainly these are not equal if base 10 is used for each. But suppose, 12 was a base 3 number and 5 was a base 6 number then, 12 base 3 = 1 x 3¹ + 2 x 3⁰, or 5 base 6 or base 10 (5 in any base is equal to 5 base 10). So, 12 and 5 can be equal if you select the right bases for each of them.

Write a program to input two integers x and y and calculate the smallest base for x and smallest base for y (likely different from x) so that x and y represent the same value. The base associated with x and y will be between 1 and 20 (both inclusive). In representing these numbers, the digits 0 to 9 have their usual decimal interpretations. The upper case letters from A to J represent digits 10 to 19 respectively.

Test your program for the following data and some random data.

Sample Data

Input:
x=12, y=5

Output:
12 (base 3)=5 (base 6)

Input:
x=10, y=A

Output:
10 (base 10)=A (base 11)

Input:
x=12, y=34

Output:
~~12 (base 8) = 34 (base 2)~~
12 (base 17) = 34 (base 5)
[∵ 34 (base 2) is not valid as only 0 & 1 are allowed in base 2]

Input:
x=123, y=456

Output:
123 is not equal to 456 in any base between 2 to 20

Input:
x=42, y=36

Output:
42 (base 7) = 36 (base 8)

import java.util.Scanner;

public class KboatFindBase
{
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        System.out.print("Enter x: ");
        String x = in.nextLine();
        System.out.print("Enter y: ");
        String y = in.nextLine();
        
        int xMax = getHighestDigit(x);
        int yMax = getHighestDigit(y);
        
        boolean found = false;
        int decimalArr[] = new int[20];
        
        for (int i = xMax; i < 20; i++) {
            decimalArr[i] = convertToDecimal(x, i+1);
        }
        
        for (int i = yMax; i < 20; i++) {
            
            int t = convertToDecimal(y, i+1);
            
            for (int j = xMax; j < 20; j++) {
                if (t == decimalArr[j]) {
                    found = true;
                    System.out.println(x + " (base " + (j+1) + ") = " 
                        + y + " (base " + (i+1) + ")");
                    break;
                }
            }
            
            if (found) {
                break;
            }
        }
        
        if (!found) {
            System.out.println(x + " is not equal to " 
                        + y + " in any base\nbetween 2 to 20");
        }
    }
    
    public static int convertToDecimal(String numStr, int base) {
        int num = 0;
        int len = numStr.length();
        
        for (int i = 0; i < len; i++) {
            int mul = (int)Math.pow(base, len - i - 1);
            char ch = numStr.charAt(i);
            int d = digitValue(ch);
            num += d * mul;
        }
        
        return num;
    }
    
    public static int digitValue(char c) {
        int value = 0;
        
        if (Character.isDigit(c)) {
            value = c - '0';
        }
        else if (Character.isLetter(c) && c >= 'A' && c <= 'J') {
            value = c - 'A' + 10;
        }
        
        return value;
    }
    
    public static int getHighestDigit(String numStr) {
        int high = 0;
        int len = numStr.length();
        
        for (int i = 0; i < len; i++) {
            char ch = numStr.charAt(i);
            int d = digitValue(ch);
            if (d > high) {
                high = d;
            }
        }
        
        return high;
    }   
}