Kunal Kamble

Posted on

#LeetCode 717. 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