Convert Decimal to Binary Number

9
1

Given a non-negative decimal integer N. Return its standard binary representation as a string.

Example 1

Input: N = 54

Output: "110110"

Explanation: The 1 digits select the place values 32, 16, 4, and 2. Their sum is 54.

Example 2

Input: N = 0

Output: "0"

Explanation: Zero is represented by one binary digit, 0.

Approach

Binary place values are powers of 2. Every place to the left of the ones place has an even value, so only the rightmost bit can make the number odd. The remainder after division by 2 therefore gives that bit.

The integer quotient represents the other bits. Integer division by 2 removes the rightmost binary digit. The next remainder gives the next digit to its left. The digits are collected from right to left, so reversing them gives the final binary representation.

Algorithm

  • Return "0" immediately when the input is zero.

  • Start with an empty collection of binary digits.

  • While the current number is positive, append its remainder after dividing by 2 and continue with the integer quotient.

  • Once the quotient reaches zero, reverse the collected digits.

  • Return the reversed digits as a string.

Dry Run

Convert Decimal to Binary Number

Convert Decimal to Binary Number

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the binary representation of N.
string decimalToBinary(long long N) {
// Handle zero before extracting digits from a positive number.
if (N == 0) {
return "0";
}
string bits;
// Extract the rightmost bit and retain the higher bits as the quotient.
while (N > 0) {
bits += to_string(N % 2);
N /= 2;
}
// Put the most significant bit first.
reverse(bits.begin(), bits.end());
return bits;
}
};
// Driver code
int main() {
long long N = 54;
// instance for class Solution
Solution sol;
cout << sol.decimalToBinary(N) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(D) when each arithmetic operation is constant time, where D is the number of digits in the returned binary string, because each digit is extracted once and the reversal takes one pass.

Space Complexity: O(D) total extra storage, including the returned string, because the digit buffer and result each hold at most D characters.

Interview follow-up Questions

For N = 2ᵏ, the result is 1 followed by exactly k zeros. Only the place worth 2ᵏ contributes to the value.

Bit ManipulationTCS NQT

Read Similar Blogs

Comments0