Problem Statement

Given a non-negative integer n, print its binary representation as a string without using built-in binary conversion functions.

Examples

Example 1:

Input: n = 5
Output: 101

Explanation: 5 in binary is 101.

Example 2:

Input: n = 8
Output: 1000

Explanation: 8 in binary is 1000.

Different Approaches

1️⃣ Iterative Division

Intuition:

Every number can be represented in binary by repeatedly dividing it by 2 and storing the remainders.

The binary representation is the reverse of the remainder sequence.

Approach:

1. If n == 0, return "0".
2. While n > 0:
   1. Store n % 2 (the current bit).
   2. Divide n by 2.
3. Reverse the collected bits to get the final result.

Code:

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

string decimalToBinary(int n) {
    if (n == 0) return "0";
    
    string binary = "";
    while (n > 0) {
        binary += to_string(n % 2); // store remainder (0 or 1)
        n /= 2;
    }

    reverse(binary.begin(), binary.end()); // reverse to correct order
    return binary;
}

int main() {
    int n;
    cout << "Enter a number: ";
    cin >> n;

    string result = decimalToBinary(n);
    cout << "Binary representation: " << result << endl;

    return 0;
}

Complexity Analysis:

• Time Complexity:O(log2 n)
  • Each division by 2 reduces n logarithmically.
• Space Complexity:O(log2 n)
  • To store the binary digits.

2️⃣ Bitwise Method (Masking & Shifting)

Intuition:

Use bitwise operators to check each bit from most significant to least significant.

You determine the position of the highest bit and shift accordingly.

Approach:

1. Find the highest set bit (i.e., MSB).
2. Loop from MSB to 0:
   • Check (n >> i) & 1 to determine if bit is 0 or 1.

Code:

#include <iostream>
#include <string>

using namespace std;

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

string decimalToBinaryBitwise(int n) {
    if (n == 0) return "0";
    string binary = "";
    int msb = 31;

    for (int i = msb; i >= 0; i--) {
        binary += ((n >> i) & 1) + '0';
    }
    return binary;
}


int main() {
    cout << decimalToBinaryBitwise(8);
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log2 n)
• Space Complexity:O(log2 n)

3️⃣ Recursion

Intuition:

Recursively divide the number by 2, printing remainder in reverse order.

This mirrors the iterative division method but is handled via function calls.

Approach:

1. Base case: if n == 0, return.
2. Recursively call decimalToBinary(n / 2).
3. Print n % 2 as you unwind recursion.

Code:

#include <iostream>
using namespace std;

void printBinaryRecursive(int n) {
    if (n == 0) return;
    printBinaryRecursive(n / 2);
    cout << n % 2;
}

int main() {
    int n = 10;
    if (n == 0)
        cout << "0";
    else
        printBinaryRecursive(n);
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log2 n)
• Space Complexity:O(log2 n)
  • Due to recursion stack