Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Basics

Decimal to Binary

Easy · Basics · Asked at TCS, Infosys, Wipro, Accenture, Cognizant

Print the binary representation of n without leading zeros (print 0 for zero).

Input

A single integer n.

Output

The binary form of n.

Constraints

Repeatedly take n % 2 and divide by 2 — the remainders, read backwards, are the bits.

Example 1

Input

13

Output

1101

Example 2

Input

0

Output

0

Hints

  1. n % 2 is the last bit; n / 2 drops that bit.
  2. Collect the bits and print them in reverse. Handle n = 0 separately.

Approach

Repeatedly take n % 2 (the lowest bit) and divide by 2. The bits come out from lowest to highest, so reverse them before printing. Zero has no bits in the loop, so print "0" directly. n can be up to 10^18 — use a 64-bit type.

Complexity: O(log n) time · O(log n) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned long long n;
    cin >> n;
    if (n == 0) {
        cout << 0 << "\n";
        return 0;
    }
    string bits;
    while (n > 0) {
        bits += char('0' + n % 2);
        n /= 2;
    }
    reverse(bits.begin(), bits.end());
    cout << bits << "\n";
    return 0;
}

Python solution

n = int(input())
bits = []
while n > 0:
    bits.append(str(n % 2))
    n //= 2
print("".join(reversed(bits)) or "0")

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        if (n == 0) {
            System.out.println(0);
            return;
        }
        StringBuilder bits = new StringBuilder();
        while (n > 0) {
            bits.append(n % 2);
            n /= 2;
        }
        System.out.println(bits.reverse());
    }
}

Solve Decimal to Binary online · All practice problems