10.20 Binary Representation

10.20.1 Problem Metadata

10.20.2 Description

Given a positive integer n, return its binary representation as a string consisting of only '0' and '1'.

10.20.3 Examples

Input: n = 6
Output: "110"

Input: n = 5
Output: "101"

10.20.4 Constraints

  • 0 <= n <= 2^31 - 1

10.20.5 Solution - Iterative Division

10.20.5.1 Walkthrough

Repeatedly divide by two and track remainders. Appending each remainder to the front of the result (or using a StringBuilder and reversing) yields the binary digits from most significant to least significant.

10.20.5.2 Analysis

  • Time Complexity: O(log n) divisions
  • Space Complexity: O(log n) to store the output

10.20.5.3 Implementation Steps

  1. Handle n == 0 by returning "0".
  2. While n > 0, compute bit = n % 2 and prepend it to the answer.
  3. Update n /= 2.

10.20.5.4 Code - Java

public String computeBinary(int n) {
    if (n == 0) {
        return "0";
    }

    StringBuilder sb = new StringBuilder();
    while (n > 0) {
        sb.append(n % 2);
        n /= 2;
    }

    return sb.reverse().toString();
}