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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

1-bit and 2-bit Characters

Number: 717

Difficulty: Easy

Paid? No

Companies: IXL, Quora

Problem Description

Given a binary array bits that always ends with 0, determine if the last character is a one-bit character. In the encoding scheme, a 0 represents a one-bit character, whereas a 1 along with the bit that follows represents a two-bit character. You must decide if the array is decoded in such a way that the final character is a one-bit character.

Key Insights

  • Traverse the array from the beginning.
  • If a 1 is encountered, skip the next bit since it forms a two-bit character.
  • If a 0 is encountered, move one step.
  • The final character must be interpreted correctly: if the pointer lands on the last index, it implies that the last character is one-bit; if not, it's part of a two-bit character.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the bits array.
Space Complexity: O(1), using only constant extra space.

Solution

The approach uses a simple pointer to iterate through the given bits array. We start from the beginning and move the pointer as follows:

  • If the current bit is 1, it indicates a two-bit character, so we increment the pointer by 2.
  • If the current bit is 0, it is a one-bit character, so we increment by 1.
    The key is to check whether the pointer exactly lands on the last index when the loop finishes. If so, the last character is one-bit; otherwise, it is not. This solution is straightforward and uses constant space.

Code Solutions

# Python solution for the "1-bit and 2-bit Characters" problem
def isOneBitCharacter(bits):
    # Initialize pointer to start of bits array
    pointer = 0
    n = len(bits)
    
    # Process the bits until reaching the second last index
    while pointer < n - 1:
        # If current bit is 1, move pointer by 2 as it forms a two-bit character
        if bits[pointer] == 1:
            pointer += 2
        else:
            # If current bit is 0, move pointer by 1 as it forms a one-bit character
            pointer += 1
    # If pointer is at the last index, then last character is one-bit character
    return pointer == n - 1

# Example usage:
print(isOneBitCharacter([1, 0, 0]))  # Expected output: True
print(isOneBitCharacter([1, 1, 1, 0]))  # Expected output: False
← Back to All Questions