Any base multiplication

1. You are given a base b

2. You are given 2 numbers n1 and n2 of base b

3. You are required to multiply n1 and n2 and print the value

Input Format:

- A base b

- A number n1

- A number n2

Output:

diff of n2 & n1 in base b

Constraints:

2 <= b <= 10

0 <= n1 <= 10000

0 <= n2 <= 10000

Input: 

5

1220

31

package jan19;

public class AnyBaseMultiplication {

    public static void main(String[] args) {
        int n1b8 = 2156;
        int n2b8 = 74;
        int base = 8;

        int product = getProduct(n1b8, n2b8, base);  // O(d2 * d1) where d2 = digits of n2, d1 = digits of n1
        System.out.println(product);
    }

    /**
     * Time Complexity: O(d2 × d1), where d1 = number of digits in n1b8 and d2 = number of digits in n2b8
     * Space Complexity: O(1) – constant extra space used (no dynamic data structures)
     */
    private static int getProduct(int n1b8, int n2b8, int base) {
        int finalAns = 0, power = 0;

        while (n2b8 > 0) { // O(d2)
            int n = n2b8 % 10;
            n2b8 = n2b8 / 10;

            // single digit multiplication + positional shift
            int singleProduct = anyBaseMultiplicationSingleDigit(n1b8, n, base) * (int) Math.pow(10, power++);

            // sum of partial product with the result so far
            finalAns = getSum(finalAns, singleProduct, base); // O(d1)
        }

        return finalAns;
    }

    /**
     * Multiplies a number with a single digit in any base
     * Time Complexity: O(d1) – d1 = number of digits in n1b8
     * Space Complexity: O(1)
     */
    private static int anyBaseMultiplicationSingleDigit(int n1b8, int n, int base) {

        int carry = 0, ans = 0, power = 0, remainder = 0;

        while (n1b8 > 0) { // O(d1)
            int a = n1b8 % 10;
            n1b8 = n1b8 / 10;

            int product = a * n + carry;

            carry = (product >= base) ? product / base : 0;
            remainder = product % base;

            ans += remainder * (int) Math.pow(10, power++);
        }

        // Add leftover carry
        ans = carry != 0 ? ans + (carry * (int) Math.pow(10, power++)) : ans;

        return ans;
    }

    /**
     * Adds two numbers in a given base
     * Time Complexity: O(max(d1, d2)) – number of digits in max(n1B8, n2B8)
     * Space Complexity: O(1)
     */
    private static int getSum(int n1B8, int n2B8, int base) {
        int carry = 0, ans = 0, power = 0;

        while (n1B8 > 0 || n2B8 > 0 || carry > 0) { // O(max(d1, d2))
            int a = n1B8 % 10;
            int b = n2B8 % 10;
            n1B8 = n1B8 / 10;
            n2B8 = n2B8 / 10;

            int sum = a + b + carry;
            carry = sum / base;

            ans += (sum % base) * (int) Math.pow(10, power++);
        }

        return ans;
    }
}

📊 Time and Space Complexity Summary Table:

Operation
Time Complexity
Space Complexity
getProduct(n1, n2, base)
O(d1 × d2)
O(1)
anyBaseMultiplicationSingleDigit
O(d1)
O(1)
getSum
O(max(d1, d2))
O(1)
d1 = number of digits in n1b8
d2 = number of digits in n2b8
📊 Complexity Table
Case
Time Complexity
Space Complexity
Explanation
Best
O(d1 × d2)
O(1)
Even in the best case (e.g., multiplying by 0 or 1), we still iterate over digits of both numbers due to multiplication and addition logic.
Average
O(d1 × d2)
O(1)
Typical input: both numbers have several digits and require full traversal.
Worst
O(d1 × d2)
O(1)
Maximum digits in both inputs. Also includes carry propagation across all digits in each addition.
 
🔍 Why O(d1 × d2)?
For each digit of n2 (let’s say it has d2 digits), we:
Multiply entire n1 (d1 digits) → O(d1)
Add result to final answer → O(d1) (since result grows gradually)
So total time: d2 × O(d1) → O(d1 × d2)

🧠 Why O(1) Space?
Only a few integer variables are used (carry, power, ans).
No recursion or dynamic data structure