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
0or1.
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
- Initialize an index
ito 0. - 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).
- If the current bit is
- After processing, check if
ipoints to the last index of the array. If so, returnTrue. Otherwise, returnFalse.
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 a0:[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.