leetcode/solution/1200-1299/1256.Encode Number

comments	difficulty	edit_url	rating	source	tags
true	Medium	https://github.com/doocs/leetcode/edit/main/solution/1200-1299/1256.Encode%20Number/README_EN.md	1561	Biweekly Contest 13 Q1	Bit Manipulation Math String

1256. Encode Number 🔒

中文文档

Description

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:

<li><code>0 &lt;= num &lt;= 10^9</code></li>

Solutions

Solution 1: Bit Manipulation

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.

Python3

class Solution:
    def encode(self, num: int) -> str:
        return bin(num + 1)[3:]

Java

class Solution {
    public String encode(int num) {
        return Integer.toBinaryString(num + 1).substring(1);
    }
}

C++

class Solution {
public:
    string encode(int num) {
        bitset<32> bs(++num);
        string ans = bs.to_string();
        int i = 0;
        while (ans[i] == '0') {
            ++i;
        }
        return ans.substr(i + 1);
    }
};

Go

func encode(num int) string {
	num++
	s := strconv.FormatInt(int64(num), 2)
	return s[1:]
}

TypeScript

function encode(num: number): string {
    ++num;
    let s = num.toString(2);
    return s.slice(1);
}