Solution: Converting Decimal to Binary

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Converting Decimal to Binary

Table of Contents

Contents are not accessible

Problem Statement

Write a Recursive Procedure to Convert a Decimal Number to a Binary Equivalent.

Given a decimal number, we need to convert it to its binary representation, as explained in the following table:

Input(s)	Output(s)	Explanation
Decimal Number = 10	Binary Number = 1010	The decimal number 10 can be represented as 1010 in binary. Each digit in the binary representation corresponds to the powers of 2.
Decimal Number = 27	Binary Number = 11011	The decimal number 27 can be represented as 11011 in binary. Each digit in the binary representation corresponds to the powers of 2.
Decimal Number = 5	Binary Number = 101	The decimal number 5 can be represented as 101 in binary. Each digit in the binary representation corresponds to the powers of 2.

Constraints:

0 <= n <= 10<sup>9</sup>

Solution

The algorithm to convert a decimal number to a binary number using recursion can be defined as follows:

Step-by-Step Algorithm

Method decimalToBinary(int decimal):
- Check if decimal is 0.
  - Return "0" if true because the binary representation of 0 is "0".
- Call the helper method decimalToBinaryRec(decimal / 2) to start building the binary string.
- Append (decimal % 2) to the result of the recursive call to capture the current bit.
Recursive Method decimalToBinaryRec(int decimal):
- Base Case:
  - If decimal is 0, return "". This stops the recursion because there are no more bits to process.
- Recursive Call:
  - Call decimalToBinaryRec(decimal / 2) to process the next bit to the left by dividing decimal by 2.
- Append Current Bit:
  - Append (decimal % 2) to the result of the recursive call. This captures the current bit, either 0 or 1.
Construct the Result:
- The binary string is built as recursion unwinds, with each call contributing one bit to the final result.
Return Final Output:
- The constructed binary string is returned from the initial decimalToBinary call. This represents the complete binary representation of the input decimal.

Algorithm Walkthrough

Input: decimal = 10

Initial Call:
- decimalToBinary(10)
  - Not 0, so call decimalToBinaryRec(10 / 2) → decimalToBinaryRec(5).
  - Append (10 % 2) = 0 at the end.
Recursive Call 1 (decimal = 5):
- decimalToBinaryRec(5)
  - Not 0, so call decimalToBinaryRec(5 / 2) → decimalToBinaryRec(2).
  - Append (5 % 2) = 1 at the end.
Recursive Call 2 (decimal = 2):
- decimalToBinaryRec(2)
  - Not 0, so call decimalToBinaryRec(2 / 2) → decimalToBinaryRec(1).
  - Append (2 % 2) = 0 at the end.
Recursive Call 3 (decimal = 1):
- decimalToBinaryRec(1)
  - Not 0, so call decimalToBinaryRec(1 / 2) → decimalToBinaryRec(0).
  - Append (1 % 2) = 1 at the end.
Base Case (decimal = 0):
- decimalToBinaryRec(0) returns "".
Unwinding Recursion:
- Return from Recursive Call 3: "" + "1" → "1".
- Return from Recursive Call 2: "1" + "0" → "10".
- Return from Recursive Call 1: "10" + "1" → "101".
- Return from Initial Call: "101" + "0" → "1010".

Final Output:

The binary representation of 10 is "1010".

Example dry run to calculate Binary of 10

Code

Here is the code for this algorithm:

Python3

. . . .

Time and Space Complexity

The time complexity of the algorithm is $O(log N)$ , where N is the decimal number. This is because the algorithm divides the decimal number by 2 in each recursive call until the base case is reached.

The space complexity is $O(log N)$ as well, as the maximum depth of the recursion is determined by the number of bits required to represent the decimal number in binary.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible