Grokking Data Structures & Algorithms for Coding Interviews

0% completed

​

Solution: Decimal to Binary Conversion

Problem Statement

Given a positive integer n, write a function that returns its binary equivalent as a string. The function should not use any in-built binary conversion function.

Examples

Example 1:

Input: 2
Output: "10"
Explanation: The binary equivalent of 2 is 10.

Example 2:

Input: 7
Output: "111"
Explanation: The binary equivalent of 7 is 111.

Example 3:

Input: 18
Output: "10010"
Explanation: The binary equivalent of 18 is 10010.

Constraints:

  • 1 <= n <= 10<sup>9</sup>

Solution

We can use a stack to efficiently create the binary

.....

.....

.....

Like the course? Get enrolled and start learning!
Gildas Montcho

Gildas Montcho

· 2 years ago

In the algorithm walkthrough, at step 6:

  1. At this point, the stack contains the binary representation of the number, but in reverse order. This is because the first bit we calculated (the least significant bit, or the "rightmost" bit) is on the top of the stack, while the last bit we calculated (the most significant bit, or the "leftmost" bit) is on the bottom of the stack.

From what I understand, the first bit (the "rightmost" bit) calculated is at the bottom of the stack, and the last bit (the "leftmost" bit) is at the top of the stack.

Eg: If the number is 4:

4 % 2 = 0 => 1st bit (directly pushed onto the empty stack, so it is at the bottom of the stack, first in last out)