Cambios mínimos en una array binaria tal que XOR de subarreglos consecutivos de tamaño K tienen paridad diferente

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:
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:
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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *