This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
995. Minimum Number of K Consecutive Bit Flips
Hard
You are given a binary array 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.
Example 1:
- Input: nums = [0,1,0], k = 1
- Output: 2
- Explanation: Flip nums[0], then flip nums[2].
Example 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].
Example 3:
- 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]
Constraints:
1 <= nums.length <= 1051 <= k <= nums.length
Solution:
class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Integer
*/
function minKBitFlips($nums, $k) {
$flipped = array_fill(0, count($nums), false);
$validFlipsFromPastWindow = 0;
$flipCount = 0;
for ($i = 0; $i < count($nums); $i++) {
if ($i >= $k) {
if ($flipped[$i - $k]) {
$validFlipsFromPastWindow--;
}
}
if ($validFlipsFromPastWindow % 2 == $nums[$i]) {
if ($i + $k > count($nums)) {
return -1;
}
$validFlipsFromPastWindow++;
$flipped[$i] = true;
$flipCount++;
}
}
return $flipCount;
}
}
Contact Links
This content originally appeared on DEV Community and was authored by MD ARIFUL HAQUE
MD ARIFUL HAQUE | Sciencx (2024-06-24T16:20:22+00:00) 995. Minimum Number of K Consecutive Bit Flips. Retrieved from https://www.scien.cx/2024/06/24/995-minimum-number-of-k-consecutive-bit-flips/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.