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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= bits.length &lt;= 1000
	bits[i] is either 0 or 1.


# Dev: Chumicat
# Date: 2019/11/30
# Submission: https://leetcode.com/submissions/detail/282638543/
# (Time, Space) Complexity : O(n), O(1)

class Solution:
    def isOneBitCharacter(self, bits: List[int]) -> bool:
        """
        :type bits: List[int]
        :rtype: bool
        """
        # Important Rules:
        # 1. If bit n is 0, bit n+1 must be a new char
        # 2. If bits end with 1, last bit must be a two bit char
        #    However, this case had been rejected by question
        # 3. If 1s in row and end with 0, 
        #    we can use count or 1s to check last char
        #    If count is even, last char is "0"
        #    If count is odd,  last char is "10"
        # Strategy:
        # 1. We don't care last element, since it must be 0.
        # 2. We check from reversed, and count 1s in a row
        # 3. Once 0 occur or list end, We stop counting
        # 4. We use count to determin result
        # 5. Since we will mod count by 2, we simplify it to bool
        ret = True
        for bit in bits[-2::-1]:
            if bit: ret = not ret
            else: break
        return ret
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int ones = 0;
        //Starting from one but last, as last one is always 0.
        for (int i = bits.length - 2; i >= 0 && bits[i] != 0 ; i--) { 
            ones++;
        }
        if (ones % 2 > 0) return false; 
        return true;
    }
}
class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) 
    {
        int n = bits.size();
        if(n == 1)
            return true;
       
        int i = 0;
        while(i <= n - 2)
        {
            if(bits[i] == 0)
                i++;
            else 
                i = i + 2;
        }
        if(i <= n-1)
            return true;
        else 
            return false;
        
    }
};
/**
 * @param {number[]} bits
 * @return {boolean}
 */
var isOneBitCharacter = function(bits) {
  let i = 0;
  while (i < bits.length - 1) {
    if (bits[i] === 1) i++;
    i++;
  }
  return bits[i] === 0;
};
1-bit and 2-bit Characters