Mid/SeniorArray
Number of Times Binary String Is Prefix-Aligned
You have a 1-indexed binary string of length n where all the bits are 0 initially. We will flip all the bits of this binary string (i.e., change them from 0 to 1) one by one. You are given a 1-indexed integer array flips where flips[i] indicates that the bit at index flips[i] will be flipped in the i^th step.
A binary string is prefix-aligned if, after the i^th step, all the bits in the inclusive range [1, i] are ones and all the other bits are zeros.
Return the number of times the binary string is prefix-aligned during the flipping process.
Example 1
Input
flips = [3,2,4,1,5]Output
2The string is prefix-aligned after steps 4 and 5, so it is prefix-aligned 2 times.
Example 2
Input
flips = [4,1,2,3]Output
1The string is prefix-aligned only after step 4, so it is prefix-aligned 1 time.
Constraints
- n == flips.length
- 1 <= n <= 5 * 10^4
- flips is a permutation of the integers in the range [1, n].
Asked at 1 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.