We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Encode Number

Number: 1189

Difficulty: Medium

Paid? Yes

Companies: Quora

Problem Description

Given a non-negative integer num, return its encoding as a string. The encoding is hidden behind a secret function that can be deduced from the examples provided. In particular, you are given: • Example 1: Input: num = 23
Output: "1000" • Example 2: Input: num = 107
Output: "101100" After analyzing the examples (and an image mapping that details the conversion), one can deduce that the secret encoding works by converting (num+1) to its binary representation and then removing the most significant bit. Note that, by definition, if num is 0, the encoded string should be "0".

Key Insights

  • The encoding process is equivalent to generating the binary representation of (num + 1) and then dropping its leftmost (most significant) bit.
  • If num is 0 then (0+1) in binary is "1", and after removing the first bit, the final encoded string is defined to be "0".
  • The operation mainly involves binary manipulation, so the time complexity is proportional to the number of bits in num (O(log(num))).

Space and Time Complexity

Time Complexity: O(log(num))
Space Complexity: O(log(num))

Solution

The solution follows these steps:

  1. If num is 0, immediately return "0" because (0+1) in binary is "1", and dropping its first bit must be specially handled.
  2. Compute num+1.
  3. Convert num+1 to its binary string representation.
  4. Remove the leading character from this binary string. This is safe because for any num > 0, num+1 in binary always starts with '1'.
  5. Return the remaining substring as the encoded string.

The key data structure used is a string (to represent the binary number), and the main algorithmic idea is simple arithmetic and string manipulation based on properties of binary representation.

Code Solutions

# Python solution for the Encode Number problem

def encode(num):
    # Special case: if the input number is 0, return "0"
    if num == 0:
        return "0"
    # Compute the binary representation of (num + 1)
    binary_str = bin(num + 1)[2:]  # bin() returns '0b...' so remove the prefix using slicing
    # Remove the most significant bit (the first character of the binary string)
    return binary_str[1:]

# Example usage:
print(encode(23))  # Expected output: "1000"
print(encode(107)) # Expected output: "101100"
← Back to All Questions