ISC practical papers › ISC 2004 › Question 1

Smallest Base Problem

ISC 2004 Computer Science Practical, Question 1 · Number programs

The question

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^2 + 1 x 3^1 + 0 x 3^0), but in base 8 it is written as 14(1 x 8^1 + 4 x 8^0).

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 what happens, 12 base 3 = 1 x 3^1 + 2 x 3^0, or 5 base 6 or 5 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 alphabetic characters A through J represent digits 10 through 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 17) = 34 (base 5)

INPUT:
X = 123
Y = 456
OUTPUT:
1 2 3 is not equal to 456 in any base between 2 to 20

INPUT:
X = 42
Y = 36
OUTPUT:
42 (base 7) = 36 (base 8)

Question: ISC 2004 Computer Science Paper 2 (Practical), Question 1, set by the Council for the Indian School Certificate Examinations (CISCE). Solution and video: Vinay Singh.

Java solution

ISC2004Q1.java Download GitHub

import java.util.*;

class Base {
    private String X, Y;
    private String output;
    private boolean found;

    public Base(String X, String Y) {
        this.X = X;
        this.Y = Y;
        process();
    }

    private void process() {
        int value1, value2;
        output = "";
        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) {
                    output += X + "(base " + i + ") = " + Y + "(base " + x + ")\n";
                    found = true;
                }
                if (found)
                    break;
            }

        }
    }

    public String toString() {
        if (found)
            return output;
        else
            return X + " is not equal to " + Y + " in any base between 2 to 20";
    }

    private static int convertFromBaseNToDecimal(String number, int baseN) {
        int answer = 0;
        number = number.toUpperCase();
        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 += digit * multiplier;
        }
        return answer;
    }

    private static int maximumDigit(String strNumber) {
        int i, 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;
    }

    private static int digitValue(char c) {
        int result = 0;
        if (Character.isDigit(c))
            result = c - '0';
        else
            result = c - 'A' + 10;
        return result;
    }
}

class ISC2004Q1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        System.out.println("INPUT:");
        System.out.print("X = ");
        String X = in.nextLine();
        System.out.print("Y = ");
        String Y = in.nextLine();
        Base b = new Base(X, Y);
        System.out.println("OUTPUT:\n" + b);

        in.close();
    }
}

Smallest Base Problem

The question

Java solution

All these solutions in one free book