Domain 1EasyCORE

1-bit and 2-bit Characters

We are given an array of bits where each bit represents either a one-bit character (`0`) or part of a two-bit character (`10` or `11`). The task is to determine if the last character in the array must be a one-bit character. The input array will always end with a zero.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

717. 1-bit and 2-bit Characters

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 1
Acceptance rate: 46.9%


Problem Breakdown

We are given an array of bits where each bit represents either a one-bit character (0) or part of a two-bit character (10 or 11). The task is to determine if the last character in the array must be a one-bit character. The input array will always end with a zero.

Inputs:

  • An array of bits, where each element is either 0 or 1.

Outputs:

  • A boolean value indicating whether the last character is a one-bit character (True) or not (False).

Implicit Constraints:

  • The array will always end with a 0.
  • The length of the array is between 1 and 1000.

Intuition

A brute-force approach would involve generating all possible ways to decode the bits and checking if the last character is one-bit. However, this approach is inefficient due to its exponential time complexity.

The key insight is to traverse the array from left to right, decoding each character as either a one-bit or two-bit character. If we reach the end of the array with exactly one bit remaining, it must be a one-bit character. Otherwise, if we finish processing all bits without any bits left over, the last character cannot be a one-bit character.

Approach

  1. Initialize an index i to 0.
  2. Traverse the array:
    • If the current bit is 0, move to the next bit (i += 1).
    • If the current bit is 1, skip the next bit as well (i += 2).
  3. After processing, check if i points to the last index of the array. If so, return True. Otherwise, return False.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the bits array. We traverse each bit at most once.
  • Space Complexity: O(1). We use a constant amount of extra space.

Solution

def isOneBitCharacter(bits):
    i = 0
    while i < len(bits) - 1:
        if bits[i] == 1:
            i += 2
        else:
            i += 1
    return i == len(bits) - 1

# Example usage:
print(isOneBitCharacter([1, 0, 0]))  # Output: True
print(isOneBitCharacter([1, 1, 1, 0]))  # Output: False

Edge Cases Handled

  • Single-bit array: [0] - The last character is a one-bit character.
  • Array ending with 10: [1, 0] - The last character is a one-bit character.
  • Array ending with 11: [1, 1, 0] - The last character is not a one-bit character.
  • All bits are 1s followed by a 0: [1, 1, 1, 1, 0] - The last character is not a one-bit character.
  • Array with multiple valid decodings: [0, 1, 0, 0] - The last character is a one-bit character.