Problem Statement

Given a non-negative integer, write a program to print its binary representation.

• The binary representation should not include leading zeroes unless the number is zero itself.
• If the input number is 0, the output should simply be 0.

Examples

Example 1:

Input: n = 10
Output: 1010

Explanation: The binary representation of 10 is 1010.

Example 2:

Input: n = 0
Output: 0

Explanation: The binary representation of 0 is 0.

Different Approaches

1️⃣ Using Division and Modulo

Intuition:

A number in binary is constructed by repeatedly dividing it by 2 and noting the remainder (which is either 0 or 1). The binary digits obtained in reverse order, so we need to reverse them.

Approach:

1. Initialize an empty string or use a stack to store remainders.
2. While the number is greater than 0:
   1. Find the remainder when divided by 2 (this gives the least significant bit).
   2. Divide the number by 2.
3. Reverse the collected remainders to get the binary representation.

Code:

#include <iostream>
#include <string>
using namespace std;


string decimalToBinary(int number) {

    string binary = "";
    
    while(number != 0) {
        binary += (48 + number % 2);
        number = number / 2;
    }
    // reverse(binary.begin(), binary.end());
    
    // or
    // reversing by yourself
    int left = 0;
    int right = binary.length()-1;
    while(left < right) {
        char temp = binary[left];
        binary[left] = binary[right];
        binary[right] = temp;
        left++;
        right--;
    }
    return binary;
    
}

int main() {
    int number = 10;
    
    cout << decimalToBinary(number);

}

Complexity Analysis:

• Time Complexity: O(log2(n)), since number is halved in each iteration.
• Space Complexity: O(log2(n)), as the string holds the binary representation.

2️⃣ Using Bitwise Operations

Intuition:

Use bitwise AND and shifts to determine the binary representation of a number. Start from the most significant bit (MSB) and shift the number right to process each bit.

Approach:

1. Start from the 31st bit (for a 32-bit integer).
2. For each bit position:
   1. Use a mask 1<<i to isolate the bit at position i.
   2. Append 1 or 0 to the result depending on whether the bit is set.
3. Skip leading zeroes until the first 1 is encountered.

Code:

#include <iostream>
using namespace std;

void printBinary(int num) {
    bool leadingZerosSkipped = false; // To ignore leading zeros
    for (int i = 31; i >= 0; i--) { // Iterate from MSB to LSB
        if (num & (1 << i)) { // Check if the i-th bit is set
            cout << "1";
            leadingZerosSkipped = true;
        } else if (leadingZerosSkipped) {
            cout << "0";
        }
    }
    if (!leadingZerosSkipped) { // If the number is 0
        cout << "0";
    }
    cout << endl;
}

int main() {
    int number = 18; // Example input
    cout << "Binary representation of " << number << " is: ";
    printBinary(number);
    return 0;
}

Complexity Analysis:

• Time Complexity: O(bit_width) = O(32), for checking all 32 bits.
• Space Complexity: O(1), since no additional memory is used.

3️⃣ Using Recursion

Intuition:

The binary representation of a decimal number can be constructed by:

1. Dividing the number by 2 repeatedly to determine each binary digit, starting from the least significant bit (LSB).
2. Collecting the remainder from each division forms the binary digits in reverse order.

Recursion naturally mirrors this process:

• Each recursive step breaks the problem into a smaller subproblem by dividing the number by 2.
• The remainder from the recursive calls are concatenated to form the final binary string.

Approach:

1. Base Case:
   1. If the number is 0, return an empty string. This acts as the stopping condition for recursion.
2. Recursive Step:
   1. Divide the number by 2 and recursively call the function with the quotient.
   2. Determine the binary digit for the current step using number % 2.
3. Concatenate Results:
   1. The binary representation of a number is the result of recursively solving for higher bits (from the quotient) and appending the current digit.
4. Character Conversion:
   1. Convert the digit (integer 0 or 1) to a character using (char)(48 + digit), where 48 is the ASCII value of '0'.

Code:

#include <iostream>
using namespace std;

// Function to convert a decimal number to its binary representation using recursion
string decimalToBinaryUsingRecursion(int number) {
    // Base case: If the number is 0, return an empty string
    if (number == 0) {
        return "";
    }
    
    // Calculate the binary digit (remainder when divided by 2)
    int digit = number % 2;
    
    // Recursive call for the next higher bits (number divided by 2)
    // Append the current digit (converted to character) to the result
    return decimalToBinaryUsingRecursion(number / 2) + (char)(48 + digit);
}

int main() {
    int number = 10; // Example input: number to be converted to binary
    
    // Print the binary representation of the number
    // If the input number is 0, ensure the output is explicitly "0"
    if (number == 0) {
        cout << "0"; 
    } else {
        cout << decimalToBinaryUsingRecursion(number);
    }

    return 0;
}

Complexity Analysis:

• Time Complexity: O(log2 (n))
  • As in each step number is divided into half.
• Space Complexity: O(log2 (n))
  • Because of the recursion stack.