Dada una array binaria arr[] de longitud N , la tarea es encontrar los cambios mínimos necesarios en la array de modo que XOR de sub-arrays consecutivas de tamaño K tengan una paridad diferente.
Ejemplos:
Entrada: arr[] = {0, 1, 0, 1, 1}, K = 2
Salida: 2
Explicación:
Para la array dada anteriormente, XOR de sub-array consecutiva de tamaño 2 es: {(0, 1): 1 , (1, 0): 1, (0, 1): 1, (1, 1): 0}
Se requieren dos volteos que se pueden realizar en los siguientes índices:
Índice 0: se requiere voltear el bit de el índice 0 , de modo que XOR del primer subarreglo permanezca en 1.
Índice 1: se requiere invertir el bit del 1er índice, de modo que el XOR del segundo subarreglo se convierta en 0.
Entrada: arr[]={0 , 0, 1, 1, 0, 0}, K = 3
Salida: 1
Explicación:
Para la array anterior XOR de sub-array consecutiva de tamaño 2 es: {(0, 0, 1): 1, (0, 1, 1): 0, (1, 1, 0): 0, (1, 0, 0): 1}
Se requiere un volteo que se puede hacer en los siguientes índices:
Índice 4: Se requiere voltear el bit del 4 to índice, de modo que XOR del tercer subarreglo se convierte en 1 y XOR del cuarto subarreglo se convierte en 0.
Enfoque: para hacer la paridad diferente de subarreglos consecutivos, el arreglo total depende del primer subarreglo de tamaño K. Es decir, cada subarreglo siguiente de tamaño K debe ser la negación del subarreglo anterior.
Por ejemplo: para un arreglo de tamaño 4, tal que el subarreglo consecutivo de tamaño 2 tenga una paridad diferente:
Let the first subarray of size 2 be {1, 1}
Then the next subarray can be {0, 0}
Consecutive subarrays of size 2 in this array:
{(1, 1): 0, (1, 0): 1, (0, 0): 0}
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum flips required such that
// alternate subarrays have
// different parity
#include <iostream>
#include <limits.h>
using namespace std;
// Function to find the minimum
// flips required in binary array
int count_flips(int a[], int n, int k)
{
// Boolean value to indicate
// odd or even value of 1's
bool set = false;
int ans = 0, min_diff = INT_MAX;
// Loop to iterate over
// the subarrays of size K
for (int i = 0; i < k; i++) {
// curr_index is used to iterate
// over all the subarrays
int curr_index = i, segment = 0,
count_zero = 0, count_one = 0;
// Loop to iterate over the array
// at the jump of K to
// consider every parity
while (curr_index < n) {
// Condition to check if the
// subarray is at even position
if (segment % 2 == 0) {
// The value needs to be
// same as the first subarray
if (a[curr_index] == 1)
count_zero++;
else
count_one++;
}
else {
// The value needs to be
// opposite of the first subarray
if (a[curr_index] == 0)
count_zero++;
else
count_one++;
}
curr_index = curr_index + k;
segment++;
}
ans += min(count_one, count_zero);
if (count_one < count_zero)
set = !set;
// Update the minimum difference
min_diff = min(min_diff,
abs(count_zero - count_one));
}
// Condition to check if the 1s
// in the subarray is odd
if (set)
return ans;
else
return ans + min_diff;
}
// Driver Code
int main()
{
int n = 6, k = 3;
int a[] = { 0, 0, 1, 1, 0, 0 };
cout << count_flips(a, n, k);
}
Java
// Java implementation to find the minimum flips
// required such that alternate subarrays
// have different parity
import java.util.*;
class Count_Flips {
// Function to find the minimum
// flips required in binary array
public static int count_flips(
int a[], int n, int k){
// Boolean value to indicate
// odd or even value of 1's
boolean set = false;
int ans = 0,
min_diff = Integer.MAX_VALUE;
// Loop to iterate over
// the subarrays of size K
for (int i = 0; i < k; i++) {
// curr_index is used to iterate
// over all the subarrays
int curr_index = i, segment = 0,
count_zero = 0, count_one = 0;
// Loop to iterate over the array
// at the jump of K to
// consider every parity
while (curr_index < n) {
// Condition to check if the
// subarray is at even position
if (segment % 2 == 0) {
// The value needs to be
// same as the first subarray
if (a[curr_index] == 1)
count_zero++;
else
count_one++;
}
else {
// The value needs to be
// opposite of the first subarray
if (a[curr_index] == 0)
count_zero++;
else
count_one++;
}
curr_index = curr_index + k;
segment++;
}
ans += Math.min(count_one, count_zero);
if (count_one < count_zero)
set = !set;
// Update the minimum difference
min_diff = Math.min(min_diff,
Math.abs(count_zero - count_one));
}
// Condition to check if the 1s
// in the subarray is odd
if (set)
return ans;
else
return ans + min_diff;
}
// Driver Code
public static void main(String[] args)
{
int n = 6, k = 3;
int a[] = { 0, 0, 1, 1, 0, 0 };
System.out.println(count_flips(a, n, k));
}
}
Python3
# Python implementation to find the # minimum flips required such that # alternate subarrays have # different parity # Function to find the minimum # flips required in binary array def count_flips(a, n, k): min_diff, ans, set = n, 0, False # Loop to iterate over # the subarrays of size K for i in range(k): # curr_index is used to iterate # over all the subarrays curr_index, segment,\ count_zero, count_one =\ i, 0, 0, 0 # Loop to iterate over the array # at the jump of K to # consider every parity while curr_index < n: # Condition to check if the # subarray is at even position if segment % 2 == 0: # The value needs to be # same as the first subarray if a[curr_index] == 1: count_zero += 1 else: count_one += 1 else: # The value needs to be # opposite of the first subarray if a[curr_index] == 0: count_zero += 1 else: count_one += 1 curr_index += k segment+= 1 ans += min(count_zero, count_one) if count_one<count_zero: set = not set min_diff = min(min_diff,\ abs(count_zero-count_one)) # Condition to check if the 1s # in the subarray is odd if set: return ans else: return ans + min_diff # Driver Code if __name__ == "__main__": n, k = 6, 3 a =[0, 0, 1, 1, 0, 0] print(count_flips(a, n, k))
C#
// C# implementation to find the minimum flips
// required such that alternate subarrays
// have different parity
using System;
class Count_Flips
{
// Function to find the minimum
// flips required in binary array
static int count_flips(int []a, int n, int k)
{
// Boolean value to indicate
// odd or even value of 1's
bool set = false;
int ans = 0, min_diff = int.MaxValue;
// Loop to iterate over
// the subarrays of size K
for (int i = 0; i < k; i++) {
// curr_index is used to iterate
// over all the subarrays
int curr_index = i, segment = 0,
count_zero = 0, count_one = 0;
// Loop to iterate over the array
// at the jump of K to
// consider every parity
while (curr_index < n) {
// Condition to check if the
// subarray is at even position
if (segment % 2 == 0) {
// The value needs to be
// same as the first subarray
if (a[curr_index] == 1)
count_zero++;
else
count_one++;
}
else {
// The value needs to be
// opposite of the first subarray
if (a[curr_index] == 0)
count_zero++;
else
count_one++;
}
curr_index = curr_index + k;
segment++;
}
ans += Math.Min(count_one, count_zero);
if (count_one < count_zero)
set = !set;
// Update the minimum difference
min_diff = Math.Min(min_diff,
Math.Abs(count_zero - count_one));
}
// Condition to check if the 1s
// in the subarray is odd
if (set)
return ans;
else
return ans + min_diff;
}
// Driver Code
public static void Main(string[] args)
{
int n = 6, k = 3;
int []a = { 0, 0, 1, 1, 0, 0 };
Console.WriteLine(count_flips(a, n, k));
}
}
// This code is contributed by Yash_R
Javascript
<script>
// Javascript implementation to find the minimum flips
// required such that alternate subarrays
// have different parity
// Function to find the minimum
// flips required in binary array
function count_flips(a , n , k) {
// Boolean value to indicate
// odd or even value of 1's
var set = false;
var ans = 0, min_diff = Number.MAX_VALUE;
// Loop to iterate over
// the subarrays of size K
for (i = 0; i < k; i++) {
// curr_index is used to iterate
// over all the subarrays
var curr_index = i, segment = 0, count_zero = 0, count_one = 0;
// Loop to iterate over the array
// at the jump of K to
// consider every parity
while (curr_index < n) {
// Condition to check if the
// subarray is at even position
if (segment % 2 == 0) {
// The value needs to be
// same as the first subarray
if (a[curr_index] == 1)
count_zero++;
else
count_one++;
} else {
// The value needs to be
// opposite of the first subarray
if (a[curr_index] == 0)
count_zero++;
else
count_one++;
}
curr_index = curr_index + k;
segment++;
}
ans += Math.min(count_one, count_zero);
if (count_one < count_zero)
set = !set;
// Update the minimum difference
min_diff = Math.min(min_diff, Math.abs(count_zero - count_one));
}
// Condition to check if the 1s
// in the subarray is odd
if (set)
return ans;
else
return ans + min_diff;
}
// Driver Code
var n = 6, k = 3;
var a = [ 0, 0, 1, 1, 0, 0 ];
document.write(count_flips(a, n, k));
// This code contributed by Rajput-Ji
</script>
Producción:
1
Análisis de rendimiento:
- Complejidad del tiempo: como en el enfoque anterior, solo hay un ciclo que toma el tiempo O (N) en el peor de los casos. Por lo tanto, la Complejidad del Tiempo será O(N) .
- Complejidad del espacio auxiliar: como en el enfoque anterior, no se utiliza espacio adicional. Por lo tanto, la complejidad del espacio auxiliar será O(1) .
Publicación traducida automáticamente
Artículo escrito por jrishabh99 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA