Dada una array binaria arr[] de tamaño N y un entero positivo K , la tarea es encontrar el número mínimo de veces que se requiere voltear cualquier subarreglo de tamaño K de la array dada arr[] para hacer que todos los elementos de la array sean iguales a 1 . Si no es posible hacerlo, imprima “-1” .
Ejemplos:
Entrada: arr[] = {0, 1, 0}, K = 1
Salida: 2
Explicación:
Realice la operación en el siguiente orden:
Operación 1: Voltea todos los elementos presentes en el subarreglo {arr[0]}. Ahora, la array se modifica a {1, 1, 0}.
Operación 2: Voltear todos los elementos presentes en el subarreglo {arr[2]}. Ahora la array se modifica a {1, 1, 1}.
Por lo tanto, el número total de operaciones requeridas es 2.Entrada: arr[] = {1, 1, 0}, K = 2
Salida: -1
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice una array auxiliar , digamos isFlipped[] de tamaño N.
- Inicialice una variable, digamos ans, para almacenar el número mínimo de cambios de subarreglo de longitud K requeridos.
- Recorra la array dada arr[] usando una variable i y realice los siguientes pasos:
- Si el valor de i es mayor que 0 , actualice el valor de isFlipped[i] como (isFlipped[i] + isFlipped[i – 1])%2 .
- Compruebe si el elemento actual debe invertirse, es decir, si el valor de A[i] es 0 y isFlipped[i] no está establecido O , el valor de A[i] es 1 y isFlipped[i] está establecido, luego realice los siguientes pasos:
- Si tal subarreglo de longitud K no es posible, imprima «-1» y salga del bucle , ya que es imposible hacer que todos los elementos del arreglo sean iguales a 1 .
- Incremente ans e isFlipped[i] en 1 y disminuya isFlipped[i + K] en 1 .
- De lo contrario, continúe con la siguiente iteración .
- Después de completar los pasos anteriores, si todos los elementos de la array se pueden convertir en 1 , imprima el valor de ans como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number
// K-length subarrays required to be
// flipped to make all array elements 1
void minimumOperations(vector<int>& A, int K)
{
// Stores whether an element
// can be flipped or not
vector<int> isflipped(A.size(), 0);
// Store the required number of flips
int ans = 0;
// Traverse the array, A[]
for (int i = 0; i < A.size(); i++) {
// Find the prefix sum
// for the indices i > 0
if (i > 0) {
isflipped[i] += isflipped[i - 1];
isflipped[i] %= 2;
}
// Check if the current element
// is required to be flipped
if (A[i] == 0 && !isflipped[i]) {
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.size() - i + 1) <= K) {
cout << -1;
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i + K]
isflipped[i + K]--;
}
else if (A[i] == 1 && isflipped[i]) {
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.size() - i + 1) <= K) {
cout << -1;
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i+K]
isflipped[i + K]--;
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
vector<int> arr = { 0, 1, 0 };
int K = 1;
minimumOperations(arr, K);
return 0;
}
Java
// Java program for the above approach
class GFG
{
// Function to find the minimum number
// K-length subarrays required to be
// flipped to make all array elements 1
static void minimumOperations(int[] A, int K)
{
// Stores whether an element
// can be flipped or not
int[] isflipped = new int[A.length+1];
// Store the required number of flips
int ans = 0;
// Traverse the array, A[]
for (int i = 0; i < A.length; i++)
{
// Find the prefix sum
// for the indices i > 0
if (i > 0) {
isflipped[i] += isflipped[i - 1];
isflipped[i] %= 2;
}
// Check if the current element
// is required to be flipped
if (A[i] == 0 && isflipped[i] == 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.length - i + 1) <= K)
{
System.out.println(-1);
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i + K]
isflipped[i + K]--;
} else if (A[i] == 1 && isflipped[i] != 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.length - i + 1) <= K)
{
System.out.println(-1);
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i+K]
isflipped[i + K]--;
}
}
// Print the result
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = {0, 1, 0};
int K = 1;
minimumOperations(arr, K);
}
}
// This code is contributed by user_qa7r.
Python3
# Python3 program for the above approach # Function to find the minimum number # K-length subarrays required to be # flipped to make all array elements 1 def minimumOperations(A, K): # Stores whether an element # can be flipped or not isflipped = [0] * (len(A) + 1) # Store the required number of flips ans = 0 # Traverse the array, A[] for i in range(len(A)): # Find the prefix sum # for the indices i > 0 if (i > 0): isflipped[i] += isflipped[i - 1] isflipped[i] %= 2 # Check if the current element # is required to be flipped if (A[i] == 0 and not isflipped[i]): # If subarray of size K # is not possible, then # print -1 and return if ((len(A) - i + 1) <= K): print(-1) return # Increment ans by 1 ans += 1 # Change the current # state of the element isflipped[i] += 1 # Decrement isFlipped[i + K] isflipped[i + K] -= 1 elif (A[i] == 1 and isflipped[i]): # If subarray of size K # is not possible, then # print -1 and return if ((len(A) - i + 1) <= K): print(-1) return # Increment ans by 1 ans += 1 # Change the current # state of the element isflipped[i] += 1 # Decrement isFlipped[i+K] isflipped[i + K] -= 1 # Print the result print(ans) # Driver Code if __name__ == "__main__": arr = [0, 1, 0] K = 1 minimumOperations(arr, K) # This code is contributed by ukasp
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the minimum number
// K-length subarrays required to be
// flipped to make all array elements 1
static void minimumOperations(List<int> A, int K)
{
// Stores whether an element
// can be flipped or not
List<int> isflipped = new List<int>();
for(int i = 0; i < A.Count + 1; i++)
isflipped.Add(0);
// Store the required number of flips
int ans = 0;
// Traverse the array, A[]
for(int i = 0; i < A.Count; i++)
{
// Find the prefix sum
// for the indices i > 0
if (i > 0)
{
isflipped[i] += isflipped[i - 1];
isflipped[i] %= 2;
}
// Check if the current element
// is required to be flipped
if (A[i] == 0 && isflipped[i] == 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.Count - i + 1) <= K)
{
Console.Write(-1);
return;
}
// Increment ans by 1
ans += 1;
// Change the current
// state of the element
isflipped[i] += 1;
// Decrement isFlipped[i + K]
isflipped[i + K] -= 1;
}
else if (A[i] == 1 && isflipped[i] != 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.Count - i + 1) <= K)
{
Console.Write(-1);
return;
}
// Increment ans by 1
ans += 1;
// Change the current
// state of the element
isflipped[i] += 1;
// Decrement isFlipped[i+K]
isflipped[i + K] -= 1;
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
List<int> arr = new List<int>(){ 0, 1, 0 };
int K = 1;
minimumOperations(arr, K);
}
}
// This code is contributed by bgangwar59
Javascript
<script>
// Javascript program for the above approach
// Function to find the minimum number
// K-length subarrays required to be
// flipped to make all array elements 1
function minimumOperations(A, K)
{
// Stores whether an element
// can be flipped or not
let isflipped = [];
for (let i = 0; i < A.length + 1; i++)
{
isflipped[i] =0;
}
// Store the required number of flips
let ans = 0;
// Traverse the array, A[]
for (let i = 0; i < A.length; i++)
{
// Find the prefix sum
// for the indices i > 0
if (i > 0) {
isflipped[i] += isflipped[i - 1];
isflipped[i] %= 2;
}
// Check if the current element
// is required to be flipped
if (A[i] == 0 && isflipped[i] == 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.length - i + 1) <= K)
{
document.write(-1);
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i + K]
isflipped[i + K]--;
} else if (A[i] == 1 && isflipped[i] != 0)
{
// If subarray of size K
// is not possible, then
// print -1 and return
if ((A.length - i + 1) <= K)
{
document.write(-1);
return;
}
// Increment ans by 1
ans++;
// Change the current
// state of the element
isflipped[i]++;
// Decrement isFlipped[i+K]
isflipped[i + K]--;
}
}
// Print the result
document.write(ans);
}
// Driver Code
let arr = [ 0, 1, 0 ];
let K = 1;
minimumOperations(arr, K);
</script>
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Enfoque 2: – Ventana deslizante
C++
#include <bits/stdc++.h>
using namespace std;
int minKBitFlips(int A[], int K, int N)
{
// store previous flip events
queue<int> flip;
int count = 0;
for (int i = 0; i < N; i++)
{
// remove an item which is out range of window.
if (flip.size() > 0 && (i - flip.front() >= K)) {
flip.pop();
}
/*
In a window, if A[i] is a even number with
even times flipped, it need to be flipped again.
On other hand,if A[i] is a odd number with odd
times flipped, it need to be flipped again.
*/
if (A[i] % 2 == flip.size() % 2) {
if (i + K - 1 >= N) {
return -1;
}
flip.push(i); // insert
count++;
}
}
return count;
}
int main()
{
int A[] = { 0, 1, 0 };
int N = sizeof(A) / sizeof(A[0]);
int K = 1;
int ans = minKBitFlips(A, K, 3);
cout << ans;
return 0;
}
// This code is contributed by divyeshrabadiya07.
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static int minKBitFlips(int[] A, int K)
{
// store previous flip events
Queue<Integer> flip = new LinkedList<>();
int count = 0;
for (int i = 0; i < A.length; i++) {
// remove an item which is out range of window.
if (!flip.isEmpty() && (i - flip.peek() >= K)) {
flip.poll();
}
/*
In a window, if A[i] is a even number with
even times flipped, it need to be flipped again.
On other hand,if A[i] is a odd number with odd
times flipped, it need to be flipped again.
*/
if (A[i] % 2 == flip.size() % 2) {
if (i + K - 1 >= A.length) {
return -1;
}
flip.offer(i); // insert
count++;
}
}
return count;
}
public static void main(String[] args)
{
int[] A = { 0, 1, 0 };
int K = 1;
int ans = minKBitFlips(A, K);
System.out.println(ans);
}
}
Python3
def minKBitFlips(A, K, N): # Store previous flip events flip = [] count = 0 for i in range(N): # Remove an item which is out range of window. if (len(flip) > 0 and (i - flip[0] >= K)): flip.pop(0) """ In a window, if A[i] is a even number with even times flipped, it need to be flipped again. On other hand,if A[i] is a odd number with odd times flipped, it need to be flipped again. """ if (A[i] % 2 == len(flip) % 2): if (i + K - 1 >= N): return -1 # Insert flip.append(i) count += 1 return count # Driver code A = [ 0, 1, 0 ] N = len(A) K = 1 ans = minKBitFlips(A, K, 3) print(ans) # This code is contributed by rameshtravel07
C#
using System;
using System.Collections;
class GFG {
static int minKBitFlips(int[] A, int K)
{
// store previous flip events
Queue flip = new Queue();
int count = 0;
for (int i = 0; i < A.Length; i++)
{
// remove an item which is out range of window.
if (flip.Count > 0 && (i - (int)flip.Peek() >= K)) {
flip.Dequeue();
}
/*
In a window, if A[i] is a even number with
even times flipped, it need to be flipped again.
On other hand,if A[i] is a odd number with odd
times flipped, it need to be flipped again.
*/
if (A[i] % 2 == flip.Count % 2) {
if (i + K - 1 >= A.Length) {
return -1;
}
flip.Enqueue(i); // insert
count++;
}
}
return count;
}
static void Main() {
int[] A = { 0, 1, 0 };
int K = 1;
int ans = minKBitFlips(A, K);
Console.WriteLine(ans);
}
}
// This code is contributed by mukesh07.
Javascript
<script>
function minKBitFlips(A,K)
{
// store previous flip events
let flip = [];
let count = 0;
for (let i = 0; i < A.length; i++) {
// remove an item which is out range of window.
if (flip.length!=0 && (i - flip[0] >= K)) {
flip.shift();
}
/*
In a window, if A[i] is a even number with
even times flipped, it need to be flipped again.
On other hand,if A[i] is a odd number with odd
times flipped, it need to be flipped again.
*/
if (A[i] % 2 == flip.length % 2) {
if (i + K - 1 >= A.length) {
return -1;
}
flip.push(i); // insert
count++;
}
}
return count;
}
let A=[0, 1, 0 ];
let K = 1;
let ans = minKBitFlips(A, K);
document.write(ans);
// This code is contributed by avanitrachhadiya2155
</script>
Producción
2
Análisis de complejidad: –
Complejidad de tiempo: O(N), donde N es la longitud de la array.
Complejidad espacial: O(N).
Enfoque 3: – Codicioso
C++
#include <bits/stdc++.h>
using namespace std;
int minKBitFlips(int A[], int K, int N)
{
int temp[N];
memset(temp, 0, N);
int count = 0;
int flip = 0;
count++;
for (int i = 0; i < N; ++i) {
flip ^= temp[i];
if (A[i] == flip) { // If we must flip the
// subarray starting here...
count++; // We're flipping the subarray from
// A[i] to A[i+K-1]
if (i + K > N) {
return -1; // If we can't flip the
// entire subarray, its
// impossible
}
flip ^= 1;
if (i + K < N) {
temp[i + K] ^= 1;
}
}
}
return count;
}
int main()
{
int A[] = { 0, 1, 0 };
int N = sizeof(A) / sizeof(A[0]);
int K = 1;
int ans = minKBitFlips(A, K, N);
cout << ans;
return 0;
}
// This code is contributed by suresh07.
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static int minKBitFlips(int[] A, int K)
{
int[] temp = new int[A.length];
int count = 0;
int flip = 0;
for (int i = 0; i < A.length; ++i) {
flip ^= temp[i];
if (A[i] == flip) { // If we must flip the
// subarray starting here...
count++; // We're flipping the subarray from
// A[i] to A[i+K-1]
if (i + K > A.length) {
return -1; // If we can't flip the
// entire subarray, its
// impossible
}
flip ^= 1;
if (i + K < A.length) {
temp[i + K] ^= 1;
}
}
}
return count;
}
public static void main(String[] args)
{
int[] A = { 0, 1, 0 };
int K = 1;
int ans = minKBitFlips(A, K);
System.out.println(ans);
}
}
Python3
def minKBitFlips(A, K): temp = [0]*len(A) count = 0 flip = 0 for i in range(len(A)): flip ^= temp[i] if (A[i] == flip): # If we must flip the # subarray starting here... count += 1 # We're flipping the subarray from # A[i] to A[i+K-1] if (i + K > len(A)) : return -1 # If we can't flip the # entire subarray, its # impossible flip ^= 1 if (i + K < len(A)): temp[i + K] ^= 1 return count A = [ 0, 1, 0 ] K = 1 ans = minKBitFlips(A, K) print(ans) # This code is contributed by divyesh072019.
Javascript
<script>
function minKBitFlips(A, K)
{
let temp = new Array(A.length);
let count = 0;
let flip = 0;
for (let i = 0; i < A.length; ++i) {
flip ^= temp[i];
if (A[i] == flip) { // If we must flip the
// subarray starting here...
count++; // We're flipping the subarray from
// A[i] to A[i+K-1]
if (i + K > A.length) {
return -1; // If we can't flip the
// entire subarray, its
// impossible
}
flip ^= 1;
if (i + K < A.length) {
temp[i + K] ^= 1;
}
}
}
return count;
}
let A = [ 0, 1, 0 ];
let K = 1;
let ans = minKBitFlips(A, K);
document.write(ans);
// This code is contributed by gfgking.
</script>
C#
/*package whatever //do not write package name here */
using System;
class GFG {
static int minKBitFlips(int[] A, int K)
{
int[] temp = new int[A.Length];
int count = 0;
int flip = 0;
for (int i = 0; i < A.Length; ++i) {
flip ^= temp[i];
if (A[i] == flip) { // If we must flip the
// subarray starting here...
count++; // We're flipping the subarray from
// A[i] to A[i+K-1]
if (i + K > A.Length) {
return -1; // If we can't flip the
// entire subarray, its
// impossible
}
flip ^= 1;
if (i + K < A.Length) {
temp[i + K] ^= 1;
}
}
}
return count;
}
public static void Main(String[] args)
{
int[] A = { 0, 1, 0 };
int K = 1;
int ans = minKBitFlips(A, K);
Console.Write(ans);
}
}
// This code is contributed by shivanisinghss2110
Producción
2
Análisis de complejidad: –
Complejidad de tiempo: O(N), donde N es la longitud de la array.
Complejidad espacial: O(N).
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array
Publicación traducida automáticamente
Artículo escrito por maxfiftychar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA