Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Decimal to Binary

Try it yourself
EasyProblem

Description

Given a non-negative integer n, return its binary representation as a string, with no leading zeros. 0 is written "0".

Examples

Example 1

Input: n = 10

Output: "1010"

Explanation: 10 = 8 + 2, so the bits for 8 and 2 are 1 and the others 0: 1010.

Example 2

Input: n = 5

Output: "101"

Explanation: 5 = 4 + 1, so 101.

Example 3

Input: n = 0

Output: "0"

Explanation: 0 is written as a single 0.

Example 4

Input: n = 1

Output: "1"

Explanation: 1 is a single 1 bit.

Constraints

  • 0 ≤ n ≤ 10^9

Editorial

Approach - Halve and Keep the Remainder

Intuition

In binary, the last bit says whether n is odd: it's n % 2. Halving with n // 2 drops that bit, and the remainder of the half is the next bit along. So divide by 2 until nothing is left, collecting the remainders.

They come out lowest bit first, the reverse of how a number is written, so read them backwards at the end. And 0, where the loop never runs, is written "0".

Step-by-Step Explanation

Let's trace Example 1, n = 10:

  1. 10 % 2 = 0, then 10 // 2 = 5.
  2. 5 % 2 = 1, then 5 // 2 = 2.
  3. 2 % 2 = 0, then 2 // 2 = 1.
  4. 1 % 2 = 1, then 1 // 2 = 0.
  5. n is 0: stop. The remainders were 0, 1, 0, 1, lowest bit first, so read backwards: "1010".

Halve and Keep the Remainder — Each step's remainder is the next bit up; at the end they're read backwards.

Algorithm

  1. If n is 0, return "0".
  2. While n > 0: collect n % 2, then set n to n // 2.
  3. Return the collected bits in reverse order, as a string.

Code

class Solution {
public:
    string decimalToBinary(int n) {
        if (n == 0) return "0";
        string bits;
        while (n > 0) {
            bits += char('0' + n % 2);      // the lowest bit
            n /= 2;
        }
        reverse(bits.begin(), bits.end());
        return bits;
    }
};

class Solution:
    def decimalToBinary(self, n: int) -> str:
        if n == 0:
            return "0"
        bits = []
        while n > 0:
            bits.append(str(n % 2))         # the lowest bit
            n //= 2
        return "".join(reversed(bits))

class Solution {
    public String decimalToBinary(int n) {
        if (n == 0) return "0";
        StringBuilder bits = new StringBuilder();
        while (n > 0) {
            bits.append(n % 2);             // the lowest bit
            n /= 2;
        }
        return bits.reverse().toString();
    }
}

var decimalToBinary = function(n) {
    if (n === 0) return "0";
    const bits = [];
    while (n > 0) {
        bits.push(n % 2);                   // the lowest bit
        n = Math.floor(n / 2);
    }
    return bits.reverse().join("");
};

Complexity Analysis

Time Complexity: O(log n)

Each step halves n, so it runs once per bit: about 30 times for 10^9.

Space Complexity: O(log n)

One character per bit of the answer.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Not handling 0. while n > 0:

On n = 0 it returns ""; the answer is "0". The loop runs while n is above 0, so for 0 it never runs and the string stays empty. 0 is written "0": it needs its own case.

Forgetting to reverse. return "".join(bits)

On n = 10 it returns "0101"; the answer is "1010". The first remainder is the lowest bit, the one on the right. Collected in order, the bits come out backwards, so they have to be read in reverse.

Stopping at 1. while n > 1:

On n = 10 it returns "010"; the answer is "1010". while n > 1 stops one step early: when n reaches 1 that 1 is the top bit, and it's never written. The loop has to run until n is 0.

Where This Pattern Is Taught

This problem practises a loop that divides until nothing is left, with % and integer division. It's taught in Python for DSA, Java for DSA, C++ for DSA and JavaScript for DSA.