1-bit and 2-bit Characters

Problem Description

We have two special characters:

• The first character can be represented by one bit 0.
• The second character can be represented by two bits (10 or 11).

Given a binary array bits that ends with 0, return true if the last character must be a one-bit character.

Examples

Example 1:

Input: bits = [1,0,0]
Output: true
Explanation: The only way to decode it is two-bit character and one-bit character.
So the last character is one-bit character.

Example 2:

Input: bits = [1,1,1,0]
Output: false
Explanation: The only way to decode it is two-bit character and two-bit character.
So the last character is not one-bit character.

Constraints

• 1 <= bits.length <= 1000
• bits[i] is either 0 or 1.

Solution for 1-bit and 2-bit Characters

Approach 1: Increment Pointer

Intuition and Algorithm

When reading from the i-th position, if bits[i] == 0, the next character must have 1 bit; else if bits[i] == 1, the next character must have 2 bits. We increment our read-pointer i to the start of the next character appropriately. At the end, if our pointer is at bits.length - 1, then the last character must have a size of 1 bit.

Code in Different Languages

C++

Written by @Shreyash3087

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0;
        while (i < bits.size() - 1) {
            i += bits[i] + 1;
        }
        return i == bits.size() - 1;
    }
};

Java

Written by @Shreyash3087

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            i += bits[i] + 1;
        }
        return i == bits.length - 1;
    }
}

Python

Written by @Shreyash3087

class Solution(object):
    def isOneBitCharacter(self, bits):
        i = 0
        while i < len(bits) - 1:
            i += bits[i] + 1
        return i == len(bits) - 1
        

Complexity Analysis

Time Complexity: $O(N)$

Reason: N is the length of bits.

Space Complexity: $O(1)$

Reason: the space used by i.

Approach 2: Greedy

Intuition and Algorithm

The second-last 0 must be the end of a character (or, the beginning of the array if it doesn't exist). Looking from that position forward, the array bits takes the form [1, 1, ..., 1, 0] where there are zero or more 1's present in total. It is easy to show that the answer is true if and only if there is an even number of ones present.

In our algorithm, we will find the second last zero by performing a linear scan from the right. We present two slightly different approaches below.

Code in Different Languages

C++

Written by @Shreyash3087

class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = bits.size() - 2;
        while (i >= 0 && bits[i] > 0) {
            i--;
        }
        return (bits.size() - i) % 2 == 0;
    }
};

Java

Written by @Shreyash3087

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = bits.length - 2;
        while (i >= 0 && bits[i] > 0) {
            i--;
        }
        return (bits.length - i) % 2 == 0;
    }
}

Python

Written by @Shreyash3087

class Solution(object):
    def isOneBitCharacter(self, bits):
        parity = bits.pop()
        while bits and bits.pop(): parity ^= 1
        return parity == 0

Complexity Analysis

Time Complexity: $O(N)$

Reason: N is the length of bits.

Space Complexity: $O(1)$

Reason: the space used by parity (or i).

References

• LeetCode Problem: 1-bit and 2-bit Characters

• Solution Link: 1-bit and 2-bit Characters

---

Authors:

Loading...