Watch 2 video solutions for Encode Number, a medium level problem involving Math, String, Bit Manipulation. This walkthrough by Shuo Yan has 90 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given a non-negative integer num, Return its encoding string.
The encoding is done by converting the integer to a string using a secret function that you should deduce from the following table:
Example 1:
Input: num = 23 Output: "1000"
Example 2:
Input: num = 107 Output: "101100"
Constraints:
0 <= num <= 10^9Problem Overview: Given a non‑negative integer num, return its encoded binary representation using a special rule. The encoding corresponds to the binary representation of num + 1 with the leading 1 removed. The result is returned as a string.
Approach 1: Binary Enumeration (Brute Force) (Time: O(n log n), Space: O(log n))
One way to understand the encoding rule is to generate binary strings sequentially and map them to integers. Start from an empty string, then enumerate binary values like "", "0", "1", "00", "01", and so on. Each step corresponds to increasing numbers. If you iterate through integers and simulate this mapping until reaching num, you can return the corresponding encoded value. This works but is inefficient because you repeatedly construct binary strings and maintain the sequence ordering. The approach mainly helps reveal the pattern behind the encoding rather than serving as a practical implementation.
Approach 2: Bit Manipulation Trick (Optimal) (Time: O(log n), Space: O(log n))
The encoding rule becomes simple once you observe the pattern: every encoded string corresponds to the binary form of num + 1 with the most significant bit removed. Compute num + 1, convert it to binary, then drop the first character. For example, if num = 23, then num + 1 = 24, which is 11000 in binary. Removing the leading 1 produces 1000, the encoded result. This works because the encoding sequence effectively enumerates binary numbers without their leading bit. The algorithm uses simple bit manipulation or binary conversion from math properties, and the result is returned as a string.
The implementation is straightforward: increment the number, convert it to binary, and slice the string starting from index 1. The runtime depends on the number of bits in num, which is O(log n). Space complexity is also O(log n) due to the binary string.
Recommended for interviews: Interviewers expect the bit manipulation observation. Brute force enumeration demonstrates reasoning about the encoding sequence, but recognizing that the sequence equals binary(num + 1) without the leading bit shows strong pattern recognition and comfort with binary representations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Binary Enumeration (Brute Force) | O(n log n) | O(log n) | Useful for understanding how the encoding sequence is formed |
| Bit Manipulation Trick | O(log n) | O(log n) | Best approach for production and interviews; uses binary representation of n+1 |