Convert Decimal to Binary Number

Problem Statement: Convert decimal to binary number.

Examples:

Example 1:
Input: N = 15
Output: 1111
Explanation: 15 in binary is represented as "1111".

Example 2:
Input: 18
Output: 10010
Explanation: 18 in binary is represented as "10010".

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Solution 1:

Intuition: Since each number can be represented by the sum of the powers of 2s, we simply have to check from 2^0 to 2^32 if the decimal number is divisible by 2^i or not.

Approach:

Take an array to store the binary number.
Now check if the decimal number is divisible by 2 or not.
If it is divisible by 2,then ith index will be 0,else ith index will be 1.
Now divide n by 2 and move to the next index.
Repeat the above steps till n becomes 0.
Now our binary number is stored in the array but in reverse order.
Print the array in reverse order.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 28;
	int binary[32] = {0};
	int pow = 1;
	int i = 0;
	while (n) {
		binary[i] = n % 2;
		i++;
		n /= 2;
	}
	for (int ind = i - 1; ind >= 0; ind--) {
		cout << binary[ind];
	}
}

Output:

11100

Time Complexity: O(logN)

Space Complexity: O(32).

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 28;
    int[] binary = new int[32];
    int pow = 1;
    int i = 0;
    while (n > 0) {
      binary[i] = n % 2;
      i++;
      n /= 2;
    }
    for (int ind = i - 1; ind >= 0; ind--) {
      System.out.print(binary[ind]);
    }
  }
}

Output:

11100

Time Complexity: O(logN)

Space Complexity: O(32).

Solution 2:Using bitwise operator(space-optimized)

Intuition: Using the “>>” operator check if the 0th,1st….32nd bit is set or not.

Approach:

By using right shift operator move to the ith bit.
Now using “and” operator check if the bit is set or not.
If bit is set print 1,else print 0.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n = 28,flag=0;
	for (int i = 32; i >= 0; i--) {
		if ((n >> i) & 1) {
		    flag=1;
			cout << 1;
		}
		else {
		    if(flag==1)
			cout << 0;
		}
	}
}

Output:

11100

Time Complexity: O(32).

Space Complexity: O(1).

Java Code

public class Main {
  public static void main(String args[]) {
    int n = 28;
    int flag=0;
    for (int i = 32; i >= 0; i--) {
      int k = n >> i;
      if ((k & 1) > 0) {
          flag=1;
        System.out.print(1);
      } else {
          if(flag==1)
        System.out.print(0);
      }
    }
  }
}

Output:

11100

Time Complexity: O(32).

Space Complexity: O(1).

Special thanks to Pranav Padawe for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article