Base – ISC Computer Science Practical 2004

The following question was asked in ISC Computer Science Practical (Paper 2) Examination in 2004. The question originally appeared in ACP-ICPC. Source.

Find the base

Numbers have different representations depending on the bases on which they are expressed.
For example, in base 3, number 12 is written as 110 but in base 8 it is written as 14.

For this problem your program will presented with a sequence of pairs of integers. Let’s call the members of a pair X and Y.
What your program is to do is determine the smallest base for X and the smallest base for Y (likely different from that for X) so that X and Y represent the same value.

base

base

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?
12 base 3 = 1 Γ— 3 + 2 Γ— 1, or 5 base 10, and certainly 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!

Input:

On each line of the input data there will be a pair of integers, X and Y, separated by one or more blanks; leading and trailing blanks may also appear on each line, are to be ignored.

The bases associated with X and Y will be between 1 and 36 (inclusive), and as noted above, need not be the same for X and Y.

In representing these numbers the digits 0 through 9 have their usual decimal interpretations.

The uppercase alphabetic characters A through Z represent digits with values 10 through 35, respectively.

The last line of the input will contain nothing but zero or more blanks (and an end of line, of course), and represents the end of the data.

There will be no incorrectly formatted data in the input.

Output:

For each pair of integers in the input display a message similar to those shown in the examples shown below.
Of course if the two integers cannot be equal regardless of the assumed base for each, then print an appropriate message; a suitable illustration is given in the examples.

Sample Input:

12 5
10 A
12 34
123 456
1 2
10 2

Sample Output:

12 (base 3) = 5 (base 6)
10 (base 10) = A (base 11)
12 (base 17) = 34 (base 5)
123 is not equal to 456 in any base 2..36
1 is not equal to 2 in any base 2..36
10 (base 2) = 2 (base 3)

Solution in Java

import java.util.Scanner;
class Base {
    private static int convertFromBaseNToDecimal(String number, int baseN) {
        number=number.toUpperCase();
        int answer=0;
        int length=number.length();
        int digit, multiplier;
        for(int i=0;i<length;i++){
            multiplier=(int)Math.pow(baseN,length-i-1);
            if(Character.isDigit(number.charAt(i))){
                digit=(number.charAt(i)-'0');
            }else{
                digit=(number.charAt(i)-55);
            }
            answer=answer+digit*multiplier;
        }
        return answer;
    }
    private static int digitValue(char c){
         int result=0;
         if (Character.isDigit(c)) result= c-'0';
         else if(Character.isLetter(c)) result= c-'A'+10;
         return result;
    } 
    private static int maximumDigit(String strNumber){
       int i=0,result=0,l=strNumber.length();
       int digit;
       for(i=0;i<=l-1;i++){ digit= digitValue(strNumber.charAt(i)) ; if(digit>result) result=digit;
       }
       return result; 
    }
    
    public static void main(String args[]) {
        
        Scanner s = new Scanner(System.in);
        System.out.println("Enter X: ");
        String X = s.nextLine();

        System.out.println("Enter Y: ");
        String Y = s.nextLine();
        
        int value1, value2;
        boolean found = false;
        int initial_i=maximumDigit(X)+1;
        int initial_x=maximumDigit(Y)+1;
        for (int i = initial_i; i <= 20; i++) {
            value1 = convertFromBaseNToDecimal(X, i);
            for (int x = initial_x; x <= 20; x++) {
                value2 = convertFromBaseNToDecimal(Y, x);
                if (value1==value2) {
                    System.out.println(X + "(base " + i + ")=" + Y + "(base "
                            + x + ") ");
                    found = true;
                    break;
                }
            }
            if(found) break;
        }
        if (!found) {
            System.out.println(X + " is not equal to " + Y
                    + " in any base between 2 to 20.");
        }  
    }
}