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!

Darshana Hettiarachchi

· 2 years ago

Show 1 reply

Mohammed Dh Abbas

· 2 years ago

class Solution: 
    def decimalToBinary(self, num):
        stack = []
        while num > 0:
            stack.append(str(num % 2))
            num = num // 2
        stack.reverse()
        return ''.join(stack)

Leopoldo Hernandez

· 2 years ago

class Solution2:
    def decimalToBinary(self, num):
        # 2 Approach two is to simply create a string with the remainders on our first loop
        new_num = ''
        while num > 0:
            new_num = str(num % 2) + new_num
            num = num // 2
        return new_num

Show 1 reply

Rohit Nair

· 2 years ago

import math
class Solution: 
    def decimalToBinary(self, num):
        def _helper(n):
            if n == 0:
                return []
            return _helper(n//2) + [str(n%2)]
        return "".join(_helper(num))

Kurt Medley

· 2 years ago

I'm not sure if I'm missing something but I'm not able to use Golang's standard libraries (fmt, strconv, etc.) in the inline problem editor which makes doing things like converting int to string difficult. Additionally, I can't print to stdout, etc. I do see fmt being used in the solution. Basically, this forced me to do some weird stuff like converting strings to bytes to avoid costly string concatenation.

```go
type Solution struct{}

// type Stack struct {
//  items []interface{}
// }

// func NewStack() Stack {
//  return Stack{}
// }

// func (s *Stack) Empty() bool {
//  return len(s.items) == 0
// }

// func (s *Stack) Push(item interface{}) {
//  s.items = append(s.items, item)
// }

// func (s *Stack) Pop() (interface{}, error) {
//  if s.Empty() {

Show 1 reply

Kurt Medley

· 2 years ago

According to GPT

```go
for len(stack) > 0 {
    pop := stack[len(stack)-1] // Pop the top element from the stack.
    stack = stack[:len(stack)-1] // Remove the popped element from the stack.
    sb += fmt.Sprintf("%d", pop) // Append the popped binary digit to the result string.
}




**Time Complexity:**

- **Stack Operations:** Popping from a slice is O(1).
- **String Concatenation:** Each `sb += fmt.Sprintf("%d", pop)` operation involves concatenating a string to `sb`. Concatenating strings in Go with `+=` within a loop has O(k) complexity where `k` is the length of the string being concatenated, leading to O(log₂(num)²) due to repeated reallocation and copying of the string.

Gildas Montcho

· 2 years ago