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

1-bit and 2-bit Characters

Difficulty: Easy

Problem Description

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character. The first character can be represented by one bit 0, while the second character can be represented by two bits (10 or 11).

Key Insights

  • The last character in the binary array is guaranteed to be a one-bit character if the last segment of bits before the terminating 0 does not start with 1.
  • If there's a 1 followed by another bit, it represents a two-bit character, which affects the decoding of the last character.
  • We can iterate from the end of the array to determine how many bits we need to skip based on the presence of 1s.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To solve this problem, we can traverse the given binary array from the end towards the beginning. We will keep track of whether we encounter a 1 followed by a 0 or 1. If we find a 1, we skip the next bit since it forms a two-bit character. If we find a 0 and have not encountered a 1 before it, we can conclude that the last character must be a one-bit character.

Code Solutions

def isOneBitCharacter(bits):
    n = len(bits)
    i = 0
    while i < n - 1:
        if bits[i] == 1:
            i += 2  # Skip the next bit as it's part of a two-bit character
        else:
            i += 1  # Move to the next bit
    return i == n - 1  # Check if we ended on the last character
← Back to All Questions