1-bit and 2-bit Characters

Easy
1836.

1-bit and 2-bit Characters

1-bit and 2-bit Characters is an easy coding problem on arrays, asked in Amazon and Google interviews.

A code has two kinds of characters: a one-bit character written as 0, and two-bit characters written as 10 or 11.

You are given a bit array bits that ends with 0 and is a valid encoding of some text. Return true if its last character must be a one-bit character, and false otherwise.

Example 1

Input
bits = [1,1,0]
Output
true
Explanation
It decodes as `11` then `0`.

Example 2

Input
bits = [0,1,0]
Output
false
Explanation
It decodes as `0` then `10` — the final `0` belongs to a two-bit character.

Example 3

Input
bits = [0]
Output
true

Constraints

  • 1 <= bits.length <= 1000
  • bits[i] is either 0 or 1
  • bits[bits.length - 1] == 0
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} bits
 * @return {boolean}
 */
var isOneBitCharacter = function(bits) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

1-bit and 2-bit Characters — Solution in Python, Java & C++

1-bit and 2-bit Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays.

1-bit and 2-bit Characters is an easy coding problem on arrays, asked in Amazon and Google interviews.

  • Difficulty: Easy
  • Topics: Arrays
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A code has two kinds of characters: a one-bit character written as 0, and two-bit characters written as 10 or 11.

You are given a bit array bits that ends with 0 and is a valid encoding of some text. Return true if its last character must be a one-bit character, and false otherwise.

Example 1

Input: bits = [1,1,0]
Output: true
Explanation: It decodes as `11` then `0`.

Example 2

Input: bits = [0,1,0]
Output: false
Explanation: It decodes as `0` then `10` — the final `0` belongs to a two-bit character.

Example 3

Input: bits = [0]
Output: true

Constraints

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

Hints for 1-bit and 2-bit Characters

  1. Hint 1

    Decoding from the left is unambiguous: a 0 is always a whole character, and a 1 always starts a two-bit character that swallows the next bit.

  2. Hint 2

    Walk with an index: step 1 on a 0, step 2 on a 1. Where does the walk land just before the end?

  3. Hint 3

    The last character is one bit exactly when the walk lands on index n - 1.

How to solve 1-bit and 2-bit Characters

The encoding is prefix-free, so a single left-to-right walk decodes it. The question is only whether some character starts at the final index.

Approach

  1. Set i = 0.
  2. While i < n - 1: advance i by bits[i] + 1 (1 for a 0, 2 for a 1).
  3. Return i == n - 1.

Why it works

At every step i is the start of a character, because 0 is a complete character and 1 must begin a two-bit one. The loop stops when i reaches n - 1 (a character starts at the last bit, and since it is 0, that character is one bit) or n (the last bit was the second half of a two-bit character).

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • Looking only at bits[n - 2] is wrong: [1,1,0] has a 1 there but the answer is true.
  • An equivalent shortcut counts the run of 1s just before the last 0: an even count means true.

Reference solution

Python

from typing import List

def isOneBitCharacter(bits: List[int]) -> bool:
    i, n = 0, len(bits)
    while i < n - 1:
        i += bits[i] + 1
    return i == n - 1

Java

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

C++

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

JavaScript

var isOneBitCharacter = function(bits) {
    var i = 0, n = bits.length;
    while (i < n - 1) i += bits[i] + 1;
    return i === n - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays