Solution Converting Decimal to Binary

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:

Constraints:

• 0 <= n <= 10⁹

Solution

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

Step-by-Step Algorithm

1. 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.

2. 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.

3. Construct the Result:

   • The binary string is built as recursion unwinds, with each call contributing one bit to the final result.

4. 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

1. Initial Call:

   • decimalToBinary(10)
     • Not 0, so call decimalToBinaryRec(10 / 2) → decimalToBinaryRec(5).
     • Append (10 % 2) = 0 at the end.

2. Recursive Call 1 (decimal = 5):

   • decimalToBinaryRec(5)
     • Not 0, so call decimalToBinaryRec(5 / 2) → decimalToBinaryRec(2).
     • Append (5 % 2) = 1 at the end.

3. Recursive Call 2 (decimal = 2):

   • decimalToBinaryRec(2)
     • Not 0, so call decimalToBinaryRec(2 / 2) → decimalToBinaryRec(1).
     • Append (2 % 2) = 0 at the end.

4. Recursive Call 3 (decimal = 1):

   • decimalToBinaryRec(1)
     • Not 0, so call decimalToBinaryRec(1 / 2) → decimalToBinaryRec(0).
     • Append (1 % 2) = 1 at the end.

5. Base Case (decimal = 0):

   • decimalToBinaryRec(0) returns "".

6. 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".

Code

Here is the code for this algorithm:

public class Solution {

  public String decimalToBinary(int decimal) {
    if (decimal == 0) {
      return "0";
    }
    return decimalToBinaryRec(decimal / 2) + (decimal % 2); // Recursive call
  }

  private String decimalToBinaryRec(int decimal) {
    if (decimal == 0) {
      return ""; // Base case
    }
    return decimalToBinaryRec(decimal / 2) + (decimal % 2); // Recursive call
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    int[] examples = { 10, 27, 5 };

    for (int example : examples) {
      String binary = sol.decimalToBinary(example);
      System.out.println(
        "Binary representation of " + example + " is: " + binary
      );
    }
  }
}

Time and Space Complexity

The time complexity of the algorithm is , 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 as well, as the maximum depth of the recursion is determined by the number of bits required to represent the decimal number in binary.

I'm working on the problem **Solution Converting Decimal to Binary** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Explain the optimal approach to **Solution Converting Decimal to Binary** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

I'll paste my solution to **Solution Converting Decimal to Binary**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

Give me 2 problems that use the SAME underlying pattern as **Solution Converting Decimal to Binary**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.