# 1-bit and 2-bit Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/1-bit-and-2-bit-characters)
Canonical: https://scaleengineer.com/dsa/problems/1-bit-and-2-bit-characters
**Data structures:** Array
**Companies:** [IXL](https://scaleengineer.com/companies/ixl), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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`.

# Approaches
## Recursive Simulation
This approach simulates the decoding process recursively. A helper function determines if the end of the array can be reached from a given starting index. The decoding rules are applied to determine the next index to recurse on.
**Time:** O(N), where N is the length of the `bits` array. Each recursive call processes one or two elements and moves forward, so each element is visited at most once. · **Space:** O(N), where N is the length of the array. In the worst-case scenario (an array of all zeros), the recursion depth can go up to N, consuming space on the call stack.
**Pros:** Conceptually simple and directly models the problem's structure.; The logic is a straightforward translation of the decoding rules.
**Cons:** Uses O(N) space for the recursion call stack, which is less efficient than an iterative solution.; Can lead to a `StackOverflowError` for very large inputs, although not an issue with the given constraints.
### Explanation
This method uses recursion to mimic the deterministic decoding process. We define a function that takes the current index as a parameter and explores the single possible decoding path from there.

- The base cases for the recursion are crucial:
  1. If the current index is the last index of the array (`bits.length - 1`), it means we have successfully landed on the final `0`. This must be a one-bit character, so we've found a valid decoding ending with a one-bit character. We return `true`.
  2. If the current index goes beyond the array bounds (`>= bits.length`), it means the previous step led to an invalid state (e.g., a two-bit character starting at the second-to-last position). We return `false`.

- The recursive step depends on the value at the current index:
  - If `bits[index]` is `0`, we must treat it as a one-bit character and move to the next index (`index + 1`).
  - If `bits[index]` is `1`, we must treat it as a two-bit character and skip the next bit, moving to `index + 2`.

The initial call will be with `index = 0`.

```java
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        return canDecode(bits, 0);
    }

    private boolean canDecode(int[] bits, int index) {
        // Base case: If we land exactly on the last index, it must be the 1-bit '0'.
        if (index == bits.length - 1) {
            return true;
        }
        // Base case: If we overshoot, it's an invalid decoding.
        if (index >= bits.length) {
            return false;
        }

        // Recursive step based on the character type
        if (bits[index] == 0) {
            // 1-bit character, move to the next index.
            return canDecode(bits, index + 1);
        } else {
            // 2-bit character, skip the next index.
            return canDecode(bits, index + 2);
        }
    }
}
```
### Algorithm
- Define a recursive helper function `canDecode(bits, index)`.
- In `canDecode`:
  - If `index == bits.length - 1`, return `true`.
  - If `index >= bits.length`, return `false`.
  - If `bits[index] == 0`, it's a one-bit character, so recursively call `canDecode(bits, index + 1)`.
  - If `bits[index] == 1`, it's a two-bit character, so recursively call `canDecode(bits, index + 2)`.
- The initial call from the main function is `canDecode(bits, 0)`.

## Iterative Simulation (Linear Scan)
This approach iteratively simulates the decoding process from left to right using a pointer. The pointer is advanced by 1 or 2 steps depending on the bit encountered, mimicking the consumption of one-bit or two-bit characters. The final position of the pointer determines if the last character is one-bit.
**Time:** O(N), where N is the length of `bits`. We perform a single pass through the array. · **Space:** O(1), as we only use a constant amount of extra space for the pointer variable.
**Pros:** Highly efficient with O(1) space complexity.; Easy to understand and implement.; Avoids potential stack overflow issues of recursion.
**Cons:** May perform more operations than the parity check approach in cases where the number of trailing ones is small.
### Explanation
Instead of recursion, we can use a simple loop and a pointer to track our position in the array. This avoids the overhead of the call stack and is generally more efficient in terms of space.

The logic is as follows:
- We start a pointer `i` at the beginning of the array (`i = 0`).
- We iterate through the array as long as we haven't reached the last element (`i < bits.length - 1`).
- At each position `i`, we check `bits[i]`:
  - If `bits[i] == 0`, we have a one-bit character, so we advance the pointer by 1 (`i += 1`).
  - If `bits[i] == 1`, we have a two-bit character, so we advance the pointer by 2 (`i += 2`).
- The loop stops when `i` is either `bits.length - 1` or `bits.length`.
- If the final value of `i` is `bits.length - 1`, it means the decoding process perfectly landed on the last element, which must be the one-bit character `0`. We return `true`.
- If the final value of `i` is `bits.length`, it means the last character processed was a two-bit one that ended at `bits.length - 1`, so the final `0` was part of it. We return `false`.

```java
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            if (bits[i] == 1) {
                i += 2;
            } else {
                i += 1;
            }
        }
        return i == bits.length - 1;
    }
}
```
### Algorithm
- Initialize a pointer `i = 0`.
- Loop while `i < bits.length - 1`.
- Inside the loop, if `bits[i]` is `1`, increment `i` by 2.
- Otherwise (if `bits[i]` is `0`), increment `i` by 1.
- After the loop terminates, the final position of `i` determines the result. Return `true` if `i == bits.length - 1`, and `false` otherwise.

## Parity Check of Trailing Ones
This is a more clever approach that works backward from the second to last element. It relies on the observation that the decoding of the final part of the string depends on the parity of the number of consecutive `1`s just before the final `0`.
**Time:** O(k), where `k` is the number of trailing `1`s before the final `0`. In the worst case, this is O(N) if the array consists of N-1 ones followed by a zero. However, it is much faster on average than a full linear scan. · **Space:** O(1), as we only use a constant amount of extra space for the counter.
**Pros:** Potentially the fastest approach on average, as it only inspects the end of the array.; Very efficient with O(1) space complexity.; An elegant solution based on a clever observation.
**Cons:** The logic is less direct and might be harder to come up with initially compared to simulation.
### Explanation
This optimized approach focuses only on the tail of the array. The key insight is that whether the last `0` is a character by itself depends on how the preceding sequence of `1`s is decoded.

Let's consider the block of consecutive `1`s right before the final `0`. The array looks like `...X, 1, 1, ..., 1, 0`, where there are `k` ones.
- When the decoder reaches the start of this block, it will process the `k` ones.
- If `k` is an even number, the `1`s can be grouped into `k/2` pairs of `11` (or `10` if the last pair includes the final `0`, but the logic holds). After processing these pairs, the decoder's position will be exactly at the final `0`, making it a one-bit character. For example, `...0, 1, 1, 0` -> `...0`, `11`, `0`.
- If `k` is an odd number, after grouping `k-1` ones into pairs, a single `1` remains. This `1` must pair with the final `0` to form a `10` two-bit character. For example, `...0, 1, 0` -> `...0`, `10`.

Therefore, the problem simplifies to counting the number of consecutive `1`s ending at index `n-2`. If this count is even, the answer is `true`; if it's odd, the answer is `false`.

```java
class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int n = bits.length;
        int ones = 0;
        // Count the number of consecutive 1s from the second to last element backwards.
        for (int i = n - 2; i >= 0 && bits[i] == 1; i--) {
            ones++;
        }
        // If the number of consecutive 1s is even, the last character is 1-bit.
        return ones % 2 == 0;
    }
}
```
### Algorithm
- Get the length of the array, `n`.
- Initialize a counter `ones = 0`.
- Iterate backwards from `i = n - 2` down to `0`.
- As long as `bits[i]` is `1`, increment the `ones` counter and continue moving left.
- If `bits[i]` is `0`, stop the iteration.
- After the loop, check if the final count of `ones` is even. Return `true` if it is, and `false` otherwise.

# Solutions
### Java

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

```

### JavaScript

```javascript
/** * @param {number[]} bits * @return {boolean} */ var isOneBitCharacter =
  function (bits) {
    let i = 0;
    const n = bits.length;
    while (i < n - 1) {
      i += bits[i] + 1;
    }
    return i == n - 1;
  };

```

### CPP

```cpp
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 - 1;
  }
};

```

### Python

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

```