_{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-bit: $0$
- 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:

- Input:
`bits = [1, 0, 0]`

, Output:`true`

- Input:
`bits = [1, 1, 1, 0]`

, Output:`true`

- 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.

- Suppose there is one symbol / last bit then by definition it should be $0$ and 1-bit.
- 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.
- If the last bit is followed up by one then the final result depends upon a number of the subsequent ones.
- If
**odd**amount is present then the last bit cannot be a 1-bit character. - If
**even**amount is present then the last bit should be a 1-bit character

- If

```
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.

## Top comments (1)

The second example in "test + edge cases" section is:

bits = [1, 1, 1, 0], Output: true

Could you please explain how the output is True? To my understanding, in the above bits array, 11 and 10 both are 2-bit characters so the 0 at the end of the list could not be a 1-bit character. Therefore I think the output should be False.

Thanks.