Encode Number | LeetCode 1256 | C

2023-09-18
#LeetCode #C #Math #String #Bit Manipulation
LeetCode

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:

1
2
Input: num = 23
Output: "1000"

Example 2:

1
2
Input: num = 107
Output: "101100"

Constraints:

1
0 <= num <= 10^9

Approach

1
Follow the rule of encoding, we can find the lenght of the output increase by one bit after increase the number by the power of 2. So when the number is 23, we can calculate the lenght of the result by the formula 1 (+1bit) + 2 (+1bit) + 4 (+1bit) + 8 (+1bit).

Algorithm

1
2
3
4
1. Find the largest sum of power of 2 which is smaller than num.
2. We can get bit and allocate the space for the result array.
3. Fill the array with the bits of difference between temp and num.
4. Fill the beginning '0's.

Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
char * encode(int num){
    if(num == 0)  return "";
    else if (num == 1)  return "0";
    else if (num ==2)  return "1";
    int base = 1, bit = 1, temp = 0;
    while((temp+base) <= num){
        temp += base;
        base *= 2;
        bit +=1 ;
    }
    char *result = malloc(bit*sizeof(char));
    result[bit-1] = '\0';
    temp = num-temp;
    bit = bit-1;
    if(temp == 0){
        for(int i = 0;i<bit;i++)
        {
            result[i] = '0';
        }
    }
    while(temp>0){
        result[bit-1] = (temp & 1)+'0';
        temp >>=1;
        bit--;
    }
    while(bit>0)
    {
      result[--bit] = (temp & 1)+'0';
      temp >>=1;
    }
    return result;
}