STACK06 - Editorial

editorial
, ,
1

Problem Link - Convert Decimal to Binary

Problem Statement:

Let’s implement a stack using arrays to solve a classic problem: converting an integer from decimal to binary using the “divisor-remainder” method.

In this method, you repeatedly divide the decimal number by 2 and keep track of the remainders.
The remainders, when read from bottom to top, give you the binary representation of the number.

Approach:

The key idea behind this code is to use a stack to reverse the binary digits generated from a decimal number.

  1. Stack Implementation: We use an array a[] and a variable top to implement the stack, where push() adds an element and pop() removes an element from the stack. The stack stores the binary digits (remainder when dividing by 2) of the decimal number in reverse order.

  2. Decimal to Binary Conversion:

    • For each decimal number, we repeatedly divide it by 2, storing the remainder in the stack. This remainder represents the binary digits in reverse order (Least Significant Bit first).
    • After converting all digits, the binary digits are popped from the stack and printed, giving the correct order for binary representation.

  3. Edge Case: If the input decimal number is 0, the binary representation is directly printed as 0.

  4. Multiple Test Cases: The program reads multiple test cases and performs the decimal to binary conversion for each one, printing the binary result.

Time Complexity:

The time complexity is O(log₂(decimal)) for each decimal number because we divide the decimal number by 2 in each iteration, which reduces its size logarithmically.

Space Complexity:

The space complexity is O(log₂(decimal)) because the stack stores the binary digits, which are proportional to the number of digits in the binary representation of the decimal number.