Encode Number - Solution & Explanation
Problem Statement
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^9
Approach Overview
Problem 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.
Solution
We add one to num, then convert it to a binary string and remove the highest bit 1.
The time complexity is O(log n), and the space complexity is O(log n). Where n is the size of num.
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| 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 |
Video Solution
1256. Encode Number • Shuo Yan • 90 views views
Watch 1 more video solutions →Frequently Asked Questions
Is Encode Number easy or hard?
Encode Number Python/Java solution
How to solve Encode Number in O(log n)?
What is the best approach for Encode Number?
Is Encode Number asked at Google/Amazon/Meta?
What data structure is used in Encode Number?
What is the time complexity of Encode Number?
Ready to solve this problem?
Practice Encode Number with our built-in code editor and test cases.
Practice on FleetCode