Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 995 with 14 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 995 # by problem number
lcpy gen -s minimum_number_of_k_consecutive_bit_flips # by problem name
nums and an integer k.
A k-bit flip is choosing a subarray of length k from nums and simultaneously changing every 0 in the subarray to 1, and every 1 in the subarray to 0.
Return the minimum number of k-bit flips required so that there is no 0 in the array. If it is not possible, return -1.
A subarray is a contiguous part of an array.
Input: nums = [0,1,0], k = 1
Output: 2
Explanation: Flip nums[0], then flip nums[2].
Input: nums = [1,1,0], k = 2
Output: -1
Explanation: No matter how we flip subarrays of size 2, we cannot make the array become [1,1,1].
Input: nums = [0,0,0,1,0,1,1,0], k = 3
Output: 3
Explanation:
Flip nums[0],nums[1],nums[2]: nums becomes [1,1,1,1,0,1,1,0]
Flip nums[4],nums[5],nums[6]: nums becomes [1,1,1,1,1,0,0,0]
Flip nums[5],nums[6],nums[7]: nums becomes [1,1,1,1,1,1,1,1]
1 <= nums.length <= 10^51 <= k <= nums.lengthclass Solution:
# Time: O(n)
# Space: O(n)
def min_k_bit_flips(self, nums: list[int], k: int) -> int:
n = len(nums)
flip_ends: list[bool] = [False] * n
flipped = 0
flips = 0
for i, num in enumerate(nums):
if i >= k and flip_ends[i - k]:
flipped ^= 1
if (num ^ flipped) == 0:
if i + k > n:
return -1
flipped ^= 1
flip_ends[i] = True
flips += 1
return flips
| Time | Space |
|---|---|
| O(n) | O(n) |