Encode Number
Problem
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: 0 maps to "", 1 to "0", 2 to "1", 3 to "00", 4 to "01", 5 to "10", 6 to "11", 7 to "000", and so on.
num = 5"10"def encode(num):
m = num + 1
bits = bin(m)[2:]
return bits[1:]function encode(num) {
const m = num + 1;
const bits = m.toString(2);
return bits.slice(1);
}class Solution {
public String encode(int num) {
int m = num + 1;
String bits = Integer.toBinaryString(m);
return bits.substring(1);
}
}string encode(int num) {
int m = num + 1;
string bits = "";
while (m > 0) { bits = char('0' + (m & 1)) + bits; m >>= 1; }
return bits.substr(1);
}Explanation
The encoding table looks mysterious, but there is a neat pattern hiding in it. If you add one to num and write that result in binary, then erase the leading 1 bit, you get exactly the encoding.
Why does adding one help? The encodings are grouped by length: "", then "0"/"1", then the four 2-character strings, and so on. Those group sizes are 1, 2, 4, 8, ... which is exactly how binary numbers grow. Shifting by num + 1 lines our value up with a clean binary representation.
So the steps are: compute m = num + 1, get its binary string, and drop the first character with bits[1:]. Every binary number starts with a leading 1, and that leading bit is just a marker we throw away.
Example: num = 5. Then m = 6, whose binary is 110. Dropping the leading 1 leaves "10", which matches the expected output.
The whole thing is just an addition and a string slice, so it runs in time proportional to the number of bits.