Katkat
Back

Count the Steps at Which Set Bits Form an Exact Prefix of Ones

SalesforceSoftware Engineer · Other
MediumSoftware EngineerOtherCoding & Algorithms

Last updated

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.

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

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