Use the Fewest Fixed-Length Bit Flips to Make Every Bit One

Quick Overview

Use the Fewest Fixed-Length Bit Flips to Make Every Bit One. A move flips every bit in a contiguous length-k window of binary nums.

Use the Fewest Fixed-Length Bit Flips to Make Every Bit One

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Other

### Problem A move flips every bit in a contiguous length-k window of binary `nums`. Return the minimum moves needed to make all bits1, or `-1` if impossible. Windows must remain inside the array. ```cpp class Solution { public: int minKBitFlips(vector<int>& nums, int k); }; ``` ### Examples **Example 1:** ```text Input: nums = [0,0,1,1], k = 2 Output: 1 Explanation: Flipping the first two bits gives all ones, and zero flips cannot work. ``` **Example 2:** ```text Input: nums = [0,1], k = 2 Output: -1 Explanation: The only available flip alternates between[0,1] and[1,0]; neither is all ones. ``` ### Constraints - `1 <= nums.length <= 10^5`. - nums is binary. - `1 <= k <= nums.length`. ### Contract considerations The allowed operation flips exactly k bits and may overlap earlier windows. A free choice of flip sequence does not change the uniquely defined minimum-count output. ```hint Read the boundary condition Once you pass a position, which future flip starts could still change it? ``` ### Boundary reminders The allowed operation flips exactly k bits and may overlap earlier windows. A free choice of flip sequence does not change the uniquely defined minimum-count output.

Overview: Use the Fewest Fixed-Length Bit Flips to Make Every Bit One. A move flips every bit in a contiguous length-k window of binary nums.

Google logo
Google
Jun 21, 2026
hardSoftware EngineerOtherCoding & Algorithms
0
0

Problem

A move flips every bit in a contiguous length-k window of binary nums. Return the minimum moves needed to make all bits1, or -1 if impossible. Windows must remain inside the array.

class Solution {
public:
    int minKBitFlips(vector<int>& nums, int k);
};

Examples

Example 1:

Input: nums = [0,0,1,1], k = 2
Output: 1
Explanation: Flipping the first two bits gives all ones, and zero flips cannot work.

Example 2:

Input: nums = [0,1], k = 2
Output: -1
Explanation: The only available flip alternates between[0,1] and[1,0]; neither is all ones.

Constraints

  • 1 <= nums.length <= 10^5 .
  • nums is binary.
  • 1 <= k <= nums.length .

Contract considerations

The allowed operation flips exactly k bits and may overlap earlier windows. A free choice of flip sequence does not change the uniquely defined minimum-count output.

Boundary reminders

The allowed operation flips exactly k bits and may overlap earlier windows. A free choice of flip sequence does not change the uniquely defined minimum-count output.