DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for #LeetCode 717. 1-bit and 2-bit Characters
Kunal Kamble
Kunal Kamble

Posted on

#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: 00
  2. 2-bit: 1010 and 1111

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

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 0000 character so we need to choose 00 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 11 present at any indexindex in the array then that indexindex and index+1index + 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Further optimization:

Let's focus on the last bit.

  1. Suppose there is one symbol / last bit then by definition it should be 00 and 1-bit.
  2. If the last bit and second last bit are 0000 then the last bit should be 1-bit as there is no 0000 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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Thanks for reading.

Top comments (0)

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: