This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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`

).

Now given a string represented by several bits. Return whether the last character must be a one-bit character or not. The given string will always end with a zero.

**Example 1:**

Input:bits = [1, 0, 0]Output:TrueExplanation: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:FalseExplanation:The only way to decode it is two-bit character and two-bit character. So the last character is NOT one-bit character.

**Note:**

`1 <= len(bits) <= 1000`

.`bits[i]`

is always `0`

or `1`

.b'

\n\n#### Approach #1: Increment Pointer [Accepted]

\n\n\n

\n#### Approach #2: Greedy [Accepted]

\n\n\n

\n

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

**Python**

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

**Java**

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

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`bits`

. \n - \n
Space Complexity: , the space used by

\n`i`

. \n

\n

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

\n**Python**

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

**Java**

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

**Complexity Analysis**

- \n
- \n
Time Complexity: , where is the length of

\n`bits`

. \n - \n
Space Complexity: , the space used by

\n`parity`

(or`i`

). \n

\n

Analysis written by: @awice.

\n