Any base to Decimal

 

48

2

o/p= 11000

public class AnyBaseToDecimal {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int base = sc.nextInt();
        int index = 0;
        int ans = 0;
        while (num > 0) {
            int rem = num % base;
            num = num / base;
            ans += (int) Math.pow(10, index++) * rem;
        }
        System.out.println(ans);
    }
}

Time Complexity (O(log n))

1. Best Case (O(1)):

Example: Consider a single-digit number in any base (e.g., 5 in base 2).

Explanation: The loop iterates only once to process the single digit, resulting 

in constant time complexity.

2. Worst Case (O(log n)):

Example: A large number with many digits in the given base (e.g., 111111_2 in binary 

representing 63 in decimal).

Explanation: The loop needs to iterate through each digit, processing them sequentially. 

The number of iterations is roughly proportional to the logarithm of the input number n in base.

3. Average Case (O(log n)):

Explanation: Assuming a random distribution of input numbers with varying lengths, the 

average number of iterations will fall between the best and worst cases, leading to an 

average time complexity of O(log n).

Reasoning for O(log n):

In each iteration, the code divides the number (num) by the base (base). This effectively 

reduces the magnitude of num by a factor of base.

The loop continues until num becomes zero.

The number of iterations required to reach zero is roughly proportional to the logarithm 

(base 10) of the initial value n in base.

This is because the number of iterations corresponds to the number of digits required to represent n in that base.

Space Complexity (O(1))

Explanation: The code uses a constant amount of additional space for variables (index, ans, etc.) 

regardless of the input size n. String manipulation for single-digit processing in the best case 

doesn't significantly impact space complexity.

Example:

Variables like index, ans, and rem hold integer values, and their space usage doesn't grow with 

the input number.

String manipulation for single-digit processing might involve some overhead, but it's considered 

negligible for space complexity analysis.

In summary:

• The AnyBaseToDecimal class offers efficient conversion with time complexity of O(log n) due to the logarithmic relationship between iterations and input size.
• The space complexity remains O(1) as the code uses a constant amount of additional space for variables.