Cracking The Coding Interview Together – Problem 5.2: Binary to String

We have all been there: a production alert fires, and you find yourself staring at a bizarre rounding error where 0.1 + 0.2 somehow equals 0.30000000000000004. Floating-point arithmetic is one of those fundamental computer science concepts that developers often take for granted until it silently corrupts a financial ledger or throws off a physics engine. It is easy to treat doubles and floats as magic boxes, but as senior engineers, we need to understand exactly how the machine represents fractional numbers under the hood.

In this post, we are going to tackle Problem 5.2: Binary to String from Cracking the Coding Interview. This problem is a fantastic tool for demystifying binary fractions. It forces us to bridge the gap between human-readable base-10 decimals and machine-readable base-2 representations. Our shared goal today is not just to write a passing solution, but to build a deep, intuitive understanding of fractional binary math, anticipate edge cases, and write production-grade Java code that handles precision limits gracefully.

Problem Statement

The problem asks us to write a method that takes a real number (a double) strictly between 0 and 1 (e.g., 0.72) and prints its binary representation. If the number cannot be represented accurately in binary with at most 32 characters (including the "0." prefix), we must print or return "ERROR".

To make this concrete, let's define our operational goals:

• Input: A double-precision floating-point number num where 0 < num < 1.
• Output: A String representing the binary equivalent (e.g., 0.101 for 0.625).
• Constraint: If the string representation exceeds 32 characters, return "ERROR".

Analyze the Problem Together

To solve this, we first need to understand how fractional numbers are represented in binary. In our standard base-10 system, digits to the right of the decimal point represent negative powers of 10:

0.725 = (7 * 10^-1) + (2 * 10^-2) + (5 * 10^-3)

Binary fractions work exactly the same way, but they use negative powers of 2:

0.101 in binary = (1 * 2^-1) + (0 * 2^-2) + (1 * 2^-3)
                = 0.5 + 0 + 0.125
                = 0.625 in decimal

This brings us to our first major "Aha!" moment: not every decimal fraction can be represented as a terminating binary fraction. In base 10, a fraction can be represented as a terminating decimal if and only if its denominator's prime factors only divide powers of 10 (which means its prime factors can only be 2 and 5). Similarly, in base 2, a fraction can only be represented as a terminating binary fraction if its denominator's prime factors are exclusively 2.

This is why a simple number like 0.1 (which is 1/10) becomes an infinite repeating fraction in binary (0.0001100110011...). Because 10 has a prime factor of 5, it cannot be represented cleanly in base 2. This is the exact reason why we need the 32-character limit constraint; otherwise, our program would loop infinitely or run out of memory trying to represent 0.1.

Comparing Approaches

There are two primary ways we can extract the binary digits of a decimal fraction:

We will choose Approach 2 (Multiply by 2) because it is structurally cleaner and less prone to floating-point precision degradation during division.

Questions for the Interviewer

In a real interview, a senior engineer never jumps straight into coding. We ask clarifying questions to establish boundaries and show that we think about edge cases:

1. "How should we handle values outside the open interval (0, 1)?"
   Presumed Answer: The problem states the number is between 0 and 1. If we receive a value outside this range (like 0, 1, or negative numbers), we should return "ERROR".
2. "Does the 32-character limit include the '0.' prefix?"
   Presumed Answer: Yes, the entire string representation, including "0.", must be at most 32 characters. This means we have at most 30 bits available for the fractional part.
3. "Should we worry about IEEE 754 rounding errors during multiplication?"
   Presumed Answer: Yes, standard double-precision floats can introduce tiny precision errors. We should write our logic to minimize these effects, though standard double precision is usually sufficient for a 30-bit limit.

Think About the Solution

Let's design our algorithm using the multiplication-by-2 approach. Here is the step-by-step mental model:

1. Initialize a StringBuilder with "0.".
2. Set up a loop that runs as long as our input num > 0.
3. Inside the loop, check if our StringBuilder length has reached 32. If it has, and num is still greater than 0, it means we cannot represent the number accurately within the limit. Return "ERROR".
4. Multiply num by 2. Let's call this result r.
5. If r >= 1:
   • Append '1' to our string.
   • Update num to be r - 1 (removing the integer part).
6. If r < 1:
   • Append '0' to our string.
   • Update num to be r.
7. Repeat until num becomes 0 or we hit the character limit.

Let's trace this with 0.625:

• Start: num = 0.625, sb = "0."
• Iteration 1: r = 0.625 * 2 = 1.25. Since r >= 1, append '1'. num = 1.25 - 1 = 0.25. sb = "0.1"
• Iteration 2: r = 0.25 * 2 = 0.5. Since r < 1, append '0'. num = 0.5. sb = "0.10"
• Iteration 3: r = 0.5 * 2 = 1.0. Since r >= 1, append '1'. num = 1.0 - 1 = 0. sb = "0.101"
• Loop terminates because num == 0. Return "0.101".

This is incredibly clean and runs in highly predictable bounds.

Write Code and Explain

Here is the production-ready Java implementation. Note the defensive checks and clean structure:

public class BinaryToStringConverter {

    /**
     * Converts a double between 0 and 1 to its binary string representation.
     * If the representation exceeds 32 characters, returns "ERROR".
     *
     * @param num the decimal fraction to convert
     * @return the binary string representation, or "ERROR"
     */
    public static String printBinary(double num) {
        // Defensive check: input must be strictly between 0 and 1
        if (num <= 0 || num >= 1) {
            return "ERROR";
        }

        StringBuilder binary = new StringBuilder();
        binary.append("0.");

        while (num > 0) {
            /* 
             * The limit is 32 characters. 
             * Since "0." takes up 2 characters, we can have at most 30 fractional bits.
             * If we reach 32 characters and still have a remainder (num > 0), 
             * we cannot represent this number accurately within the limit.
             */
            if (binary.length() >= 32) {
                return "ERROR";
            }

            double r = num * 2;
            if (r >= 1) {
                binary.append("1");
                num = r - 1;
            } else {
                binary.append("0");
                num = r;
            }
        }

        return binary.toString();
    }

    public static void main(String[] args) {
        // Test Case 1: Terminates quickly (0.625 -> 0.101)
        System.out.println("0.625 in binary: " + printBinary(0.625));

        // Test Case 2: Terminates within limit (0.125 -> 0.001)
        System.out.println("0.125 in binary: " + printBinary(0.125));

        // Test Case 3: Does not terminate cleanly (0.123 -> ERROR)
        System.out.println("0.123 in binary: " + printBinary(0.123));
    }
}

Code Walkthrough

• Defensive Guard Clause: We immediately filter out invalid inputs. If someone passes 1.5 or -0.5, we fail fast.
• StringBuilder Optimization: We use StringBuilder instead of standard string concatenation. In Java, string concatenation in a loop creates garbage objects on the heap; StringBuilder modifies an internal char array in place.
• The 32-Character Boundary: The check binary.length() >= 32 is placed at the top of the loop. If we enter the loop with 32 characters already written, and we still have a non-zero num to process, we immediately return "ERROR". This prevents unnecessary calculations.

Time & Space Complexity

Analyzing complexity is where we show our depth. Because of the hard constraint of 32 characters, the complexity analysis here has a subtle twist:

• Time Complexity: O(1) (Constant Time). While it looks like O(N) where N is the number of bits, the loop is strictly capped at 30 iterations (32 characters minus the "0." prefix). Therefore, the execution time is bounded by a constant upper limit.
• Space Complexity: O(1) (Constant Space). The StringBuilder will hold at most 32 characters before either returning the result or failing with "ERROR". No auxiliary data structures are scaled with input size.

Why This Problem Matters (The Senior Perspective)

In enterprise software engineering, we rarely write custom binary fraction converters. However, the architectural lessons of this problem are incredibly far-reaching.

Consider IEEE 754, the standard for floating-point representation. Most modern languages represent double using 64 bits (1 sign bit, 11 exponent bits, and 52 fraction bits). Because of this finite representation, numbers that cannot be represented as a sum of powers of 2 are rounded to the nearest representable value. This rounding is tiny, but it compounds over millions of database transactions.

If you are designing a financial ledger, a billing system, or an e-commerce checkout service, using double or float is an architectural anti-pattern. Instead, we must use:

1. Arbitrary-Precision Types: In Java, this is BigDecimal. It avoids binary rounding issues by storing numbers as unscaled integers and a scale factor, performing math in base 10.
2. Integer Scaling: Store monetary values in their lowest denomination (e.g., cents instead of dollars). Instead of storing $19.99 as 19.99, store it as 1999 (an integer). This completely bypasses floating-point math.

Understanding the limitations of binary fractions allows us to make these critical architectural decisions before a single line of production code is written.

Final Thoughts

We have successfully broken down CTCI Problem 5.2, explored the mechanics of binary fractions, and written a clean, constant-time solution. The next time you see a weird rounding error in your logs, you will know exactly why it is happening: the machine is trying to fit an infinite repeating binary fraction into a finite set of bits.

If you want to take this a step further, try modifying our solution to use the alternative "division by 2" approach and see if you can spot where floating-point precision issues begin to creep in. It is a fantastic exercise in debugging.

Thanks for reading, and happy coding! We will see you in the next post on "The Dev Learnings".