#LeetCode 717. 1-bit and 2-bit Characters

_{^{Problem Link: https://leetcode.com/problems/1-bit-and-2-bit-characters}}

Hi everyone
Kunal here with a new DSA blog. This is the 1st blog in the line of blogs. Here I have described how I solved a 717. 1-bit and 2-bit Characters. LeetCode question.

Requirement:

We have two three special characters:

1. 1-bit: $0$
2. 2-bit: $10$ and $11$

From the given array of bits, we have to identify if the last character is part of a 1-bit character (i.e. only $0$ ).

Test + Edge Cases:

1. Input: bits = [1, 0, 0], Output: true
2. Input: bits = [1, 1, 1, 0], Output: true
3. Input: bits = [0, 0], Output: true There is no $00$ character so we need to choose $0$ two times.

Solution:

Here we want to confirm that the last bit in the bits array can only be part of a 1-bit character. We should identify 2-bits and 1-bits characters in the array. As per requirements, if there is $1$ present at any $index$ in the array then that $index$ and $index + 1$ should be part of 2-bit characters. So now we have simple conditions that we can check against.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        while i < len(bits):
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1

            # If at end of the list, 0 is present and not skipped 
            # Last bit should be a 1-bit character 
            elif bits[i] == 0 and i == len(bits) - 1:
                return True

            i += 1

        return False

bits[i] == 0 is redundant here cause it should be covered as an else part of bits[i] == 1. Additionally, there is no point in checking i == len(bits) - 1 in every iteration, ideally we should verify if the current (not skipped) index points to the last index of bit at the end, outside of the loop.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        i = 0
        n = len(bits)
        last = len(bits) - 1
        while i < last:
            # If 1 is present then the next bit should be part of the 2-bit character
            # So skip the next bit
            if bits[i] == 1:
                i += 1
            i += 1

        # If the last index is not skipped then it should be a 1-bit character
        return i == last

Further optimization:

Let's focus on the last bit.

1. Suppose there is one symbol / last bit then by definition it should be $0$ and 1-bit.
2. If the last bit and second last bit are $00$ then the last bit should be 1-bit as there is no $00$ character in 2-bit.
3. If the last bit is followed up by one then the final result depends upon a number of the subsequent ones.
   1. If odd amount is present then the last bit cannot be a 1-bit character.
   2. If even amount is present then the last bit should be a 1-bit character

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        n = len(bits)
        if n == 1:
            return True

        if bits[-2] == 0:
            return True

        ones = 0
        for i in range(n - 2, -1, -1):
            if bits[i] == 1:
                ones += 1
            else: break

        return ones % 2 == 0

1st and second condition in the above code is redundant as in both of them a count of one is 0 which is even. So now we should just check if the count of ones is even or odd.

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        evenOnes = True
        for bit in bits[-2::-1]:
            if bit == 1:
                evenOnes = not evenOnes
            else: break

        return evenOnes

Thanks for reading.