1-bit and 2-bit Characters
Problem
Decide if the last character of bits (which ends in 0) is a 1-bit (0) char.
bits = [1,0,0]Truedef is_one_bit_character(bits):
i = 0
while i < len(bits) - 1:
i += 2 if bits[i] == 1 else 1
return i == len(bits) - 1function isOneBitCharacter(bits) {
let i = 0;
while (i < bits.length - 1) i += bits[i] === 1 ? 2 : 1;
return i === bits.length - 1;
}boolean isOneBitCharacter(int[] bits) {
int i = 0;
while (i < bits.length - 1) i += bits[i] == 1 ? 2 : 1;
return i == bits.length - 1;
}bool isOneBitCharacter(vector& bits) {
int i = 0;
while (i < (int)bits.size() - 1) i += bits[i] == 1 ? 2 : 1;
return i == bits.size() - 1;
} Explanation
The key insight is that the characters are self-decoding as you read left to right: a 1 is always the start of a 2-bit character (10 or 11), and a 0 is always a complete 1-bit character. So there is never any guessing about how to split the array.
Because of that, we just walk a pointer i across the array, jumping 2 steps when we land on a 1 and 1 step when we land on a 0. The loop stops once i reaches the last index (we never step past it before that).
The array always ends in 0. The question is whether that final 0 got swallowed as the second bit of a 2-bit character, or whether it stands alone. If our jumps land exactly on the last index, the last character started there as a lone 0, so we return i == len(bits) - 1.
Example: bits = [1, 0, 0]. Start at i = 0, see a 1, jump to i = 2. Now i is the last index, so the final 0 is its own 1-bit character and the answer is True.