Algorithm

Problem Name: 717. 1-bit and 2-bit Characters

Problem Link: https://leetcode.com/problems/1-bit-and-2-bit-characters/
 

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.

 

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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class Solution {
public:
    bool isOneBitCharacter(vector<int>& bits) {
        int i = 0, n = bits.size();
        while(i  <  n - 1) i += bits[i] + 1;
        return i != n;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
bits = [1,0,0]

Output

x
–
+
cmd
true

#2 Code Example with Java Programming

Code - Java Programming


class Solution {
  public boolean isOneBitCharacter(int[] bits) {
    int idx = 0;
    while (idx  <  bits.length - 1) {
      if (bits[idx] != 0) {
        idx++;
      }
      idx++;
    }
    return idx == bits.length - 1;
  } 
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
bits = [1,0,0]

Output

x
–
+
cmd
true

#3 Code Example with Javascript Programming

Code - Javascript Programming


const isOneBitCharacter = function(bits) {
  let ones = 0;
  //Starting from one but last, as last one is always 0.
  for (let i = bits.length - 2; i >= 0 && bits[i] != 0; i--) {
    ones++;
  }
  return ones % 2 > 0 ? false : true;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
bits = [1,1,1,0]

Output

x
–
+
cmd
false

#4 Code Example with Python Programming

Code - Python Programming


class Solution:
    def isOneBitCharacter(self, bits):
        """
        :type bits: List[int]
        :rtype: bool
        """
        while bits:
            last=bits.pop(0)
            if last==1:bits.pop(0)
        return True if last==0 else False
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
bits = [1,1,1,0]

Output

x
–
+
cmd
false

#5 Code Example with C# Programming

Code - C# Programming


namespace LeetCode
{
    public class _0717_1BitAnd2BitCharacters
    {
        public bool IsOneBitCharacter(int[] bits)
        {
            int i = 0;
            for (; i  <  bits.Length; i++)
            {
                if (bits[i] == 1) i++;
                else
                {
                    if (i == bits.Length - 1)
                        return true;
                }
            }

            return false;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
bits = [1,0,0]

Output

x
–
+
cmd
true
Advertisements

Demonstration

Previous
#715 Leetcode Range Module Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#718 Leetcode Maximum Length of Repeated Subarray Solution in C, C++, Java, JavaScript, Python, C# Leetcode