algoadvance

We have two special characters:

• 1-bit character which is represented by a single 0.
• 2-bit character which is represented by either 10 or 11.

Given a binary array bits ending with a 0, you need to determine if the last character must be a 1-bit character or not. The task is to return True if the last character can only be a 1-bit character and False otherwise.

Example 1:

• Input: bits = [1, 0, 0]
• Output: True
• Explanation: The only way to decode it is 10, 0 where the last ‘0’ is a 1-bit character.

Example 2:

• Input: bits = [1, 1, 1, 0]
• Output: False
• Explanation: The only way to decode it is 11, 10 where the last ‘0’ is part of the 2-bit character '10'.

Clarifying Questions

1. Can the array be empty?
   • No, as per the problem the array ends with a 0 which means there is at least one element.
2. Can there be other characters besides 0 and 1?
   • No, the array strictly consists of binary digits 0 and 1 as given in the problem.
3. Should we always assume that the input array is valid given the problem constraints?
   • Yes, we assume that the constraints ensure a valid input.

Strategy

1. We need to decode the given binary array bits following the decoding rules (1-bit or 2-bit).
2. Initialize an index i and iterate through the array from the start.
3. If the current bit is a 1, increment the index i by 2 because 1 can only be part of a 2-bit character (10 or 11).
4. If the current bit is 0, increment the index i by 1 because 0 represents a 1-bit character.
5. Finally, check if at the end of the iteration, i is exactly at the last element. If yes, return True; otherwise, return False.

By this logic, we can ensure that the last character is checked correctly based on the decoding rules.

Code

def isOneBitCharacter(bits):
    i = 0
    while i < len(bits) - 1:  # Traverse until the second last element
        if bits[i] == 1:
            i += 2
        else:
            i += 1
    # If we end at the last element, it means it's a 1-bit character
    return i == len(bits) - 1

# Example Usage
print(isOneBitCharacter([1, 0, 0]))  # True
print(isOneBitCharacter([1, 1, 1, 0]))  # False

Time Complexity

The time complexity of this solution is O(n), where n is the length of the input array bits. This is because we are making a single pass through the array, looking at each element at least once.

The space complexity is O(1) because we are using a constant amount of extra space regardless of the input size.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?