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
2and 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
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 codeint 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.
Be the first to add a comment.