Count the Steps at Which Set Bits Form an Exact Prefix of Ones
Company: Salesforce
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
A binary string of length `n` has positions numbered `1` to `n`, and every bit starts as `0`. The process runs for `n` steps: at step `i` (counting from 1), the bit at position `flips[i - 1]` is set to `1`. Because `flips` is a permutation of `1` to `n`, every bit is set exactly once.
After step `i`, the string is a clean prefix when the bits at positions `1` through `i` are all `1` and every other bit is still `0`. Return the number of steps after which the string is a clean prefix.
### Function Signature
```python
def count_clean_prefix_steps(flips: List[int]) -> int:
```
### Rules
- The condition is checked once after each step, using the state after that step's bit is set.
- After the final step every bit is `1`, so that step always counts.
### Constraints
- `1 <= n == len(flips) <= 5 * 10^4`
- `flips` is a permutation of the integers `1` to `n`.
### Examples
**Example 1**
```
Input: flips = [2, 1, 3, 5, 4]
Output: 3
```
After step 1 only position 2 is set, so position 1 is missing. After steps 2 and 3 the set positions are `{1, 2}` and `{1, 2, 3}`, both clean prefixes. After step 4 position 4 is missing while position 5 is set. After step 5 all positions are set. The clean steps are 2, 3 and 5.
**Example 2**
```
Input: flips = [3, 1, 2]
Output: 1
```
Only after step 3 are exactly the first three positions set.
**Example 3**
```
Input: flips = [1, 2, 3, 4]
Output: 4
```
Overview: Array problem: the bits of an all-zero binary string are set one at a time in the order given by a permutation; count the steps after which exactly the first i bits are set. It tests careful reasoning about prefix conditions and handling large inputs efficiently.
Read the full Salesforce Software Engineer interview experience this question came from