Decimal to Binary — Editorial

Opening the reading…

Intuitioneach division reveals one binary place

A binary number is built from powers of two, just as a decimal number is built from powers of ten. When you divide an integer by 2, the remainder tells you whether its lowest binary bit is 0 or 1. The quotient contains all the higher binary places, so repeating the same operation walks through the representation one bit at a time.

The first remainder is the least significant bit, but the answer must begin with the most significant 1. Therefore, append each remainder as you divide, then reverse the collected characters. Because the process stops when the quotient becomes zero, it naturally stops immediately after the highest useful bit and never creates leading zeroes.

Approach

Create an empty string for the discovered bits, because the repeated divisions find the answer from right to left.

While n is positive, append the lowest bit of n using n & 1, because this bit is exactly the remainder of n divided by 2.

Shift n right by one position, which removes the bit just recorded and replaces n with the quotient needed for the next iteration.

Reverse the collected string, because the first character appended was the least significant bit rather than the most significant one.

Return the reversed string. Since the input is positive, the loop records at least one bit, so n = 1 correctly produces "1".

Complexitythe number of iterations is the number of binary places

MEASURE	BOUND	WHY
Time	O(log n)	Each iteration records one bit and replaces n with roughly half its previous value. The value therefore reaches zero after one iteration per binary place, and reversing the collected string touches each recorded bit once more.
Space	O(1) extra	The returned string contains O(log n) characters, but output storage is excluded from the working-space bound. The bits are reversed in place, so no additional structure grows with the input; the worst valid input simply produces the maximum 31-character output.

Here n is the positive input integer, and log n means the number of times n can be divided by 2 before reaching zero.

Annotated solutionC++ · repeated division · collect, then reverse

CPPExtract the low bit repeatedly, then reverse the complete output string.

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

class Solution {
public:
    string decToBinary(int n) {
        string bits;

        while (n > 0) {
            bits.push_back(char('0' + (n & 1)));
            n >>= 1;
        }

        reverse(bits.begin(), bits.end());
        return bits;
    }
};

The two bit operations have different jobs. n & 1 reads the bit that must be appended now, while n >>= 1 discards that bit and exposes the next one. Keeping those lines in this order matters: shifting first would lose the current lowest bit before it is recorded. The final reverse is required because extraction proceeds from low place to high place.

The highest-bit alternativea different arrangement that writes left to right

You can avoid collecting bits backward by first finding the largest power of two that does not exceed n. Then inspect powers of two from that value down to 1, appending 1 when the current power fits and subtracting it, or appending 0 otherwise. This has the same O(log n) time and O(1) extra space, but it needs an initial search and a second loop, so repeated division is usually the shorter solution.

CPPFind the highest set place, then emit every binary place from high to low.

#include <string>
using namespace std;

class Solution {
public:
    string decToBinary(int n) {
        int place = 1;
        while (place <= n / 2) {
            place *= 2;
        }

        string bits;
        while (place > 0) {
            if (n >= place) {
                bits.push_back('1');
                n -= place;
            } else {
                bits.push_back('0');
            }
            place /= 2;
        }

        return bits;
    }
};