Dada una array A de tamaño N , que tiene cada elemento 0 o 1 y un número entero K. Encuentre la cantidad mínima de elementos que deben invertirse, de modo que ningún subarreglo de tamaño mayor o igual que K tenga una media aritmética de 1.
Ejemplos:
Entrada : N = 5, A = {1, 1, 1, 1, 1}, K = 5
Salida : 1
Explicación : Inicialmente, la media de solo el subconjunto de tamaño 5 es (1+1+1+1+1 )/5 = 1. Entonces, voltee el primer elemento (es decir, hágalo 0). La array ahora se convierte en {0, 1, 1, 1, 1}, cuya media es menor que 1. Entonces, solo necesitábamos 1 vuelta para satisfacer la condición requerida.
Tenga en cuenta que {1, 1, 1, 1, 0} también satisface la condición requerida. También son posibles otras arrays.Entrada : N = 4, A = {1, 1, 0, 1}, K = 2
Salida : 1
Explicación : voltea el primer 1 (es decir, el elemento en el índice 0), para que la array resultante se convierta en {0, 1, 0, 1} en el que ningún subconjunto de tamaño 2 o más tiene una media de 1.
Tenga en cuenta que {1, 0, 0, 1} también es un posible conjunto que satisface la condición requerida.
Enfoque: Este problema se puede resolver fácilmente usando la técnica Greedy .
La observación es que una array binaria de tamaño K tiene una media aritmética igual a 1 solo si todos los K elementos en ella son iguales a 1. Además, si todas las subarreglas de tamaño K tienen un significado menor que 1, entonces todas los subconjuntos de tamaño mayor que K también habrían significado menos de 1. Por lo tanto, el siguiente enfoque se puede utilizar para resolver el problema:
- Comience a atravesar la array dada.
- mantener el conteo actual de los consecutivos hasta el índice actual en una variable, decir «contar».
- Si el elemento actual es 1, incrementamos el conteo en 1, de lo contrario lo convertimos en 0, ya que los 1 consecutivos que terminan en el i -ésimo índice se convierten en 0.
- Si el recuento se vuelve igual a K, eso significa que hay K 1 consecutivos que terminan en el índice actual, por lo que incrementamos la respuesta en 1 (eso implica que el índice actual se convertiría en 0) y nuevamente convertimos el recuento en variable 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find Minimum flips to
// Make mean of all k size
// Sub-arrays less than 1
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// Minimum flips to make
// Mean of all k size
// Subarrays less than 1
int minimumFlips(int N, int A[], int K)
{
// Initializing answer by 0
// That stores the number of flips
int answer = 0;
// Initializing count variable by 0
// That stores the number of consecutive 1s
int count = 0;
// iterating through the array
for (int i = 0; i < N; i++) {
if (A[i] == 1) {
// If current element is 1,
// We increment count by 1
count++;
// if count of consecutive 1s
// Reaches k, we increment the answer
// as the mean of the subarray from
// i-k to ith element becomes 1
if (count == K) {
answer++;
count = 0;
}
}
// else if current element is
// 0, we make count 0
else {
count = 0;
}
}
// returning the required answer
return answer;
}
// Driver Code
int main()
{
int N = 5, K = 5;
int A[] = { 1, 1, 1, 1, 1 };
int minimum_flips = minimumFlips(N, A, K);
cout << minimum_flips;
}
Java
// Java program to find Minimum flips to
// Make mean of all k size
// Sub-arrays less than 1
import java.io.*;
class GFG {
// Function to calculate
// Minimum flips to make
// Mean of all k size
// Subarrays less than 1
static int minimumFlips(int N, int A[], int K)
{
// Initializing answer by 0
// That stores the number of flips
int answer = 0;
// Initializing count variable by 0
// That stores the number of consecutive 1s
int count = 0;
// iterating through the array
for (int i = 0; i < N; i++)
{
if (A[i] == 1)
{
// If current element is 1,
// We increment count by 1
count++;
// if count of consecutive 1s
// Reaches k, we increment the answer
// as the mean of the subarray from
// i-k to ith element becomes 1
if (count == K) {
answer++;
count = 0;
}
}
// else if current element is
// 0, we make count 0
else {
count = 0;
}
}
// returning the required answer
return answer;
}
// Driver Code
public static void main (String[] args) {
int N = 5, K = 5;
int A[] = { 1, 1, 1, 1, 1 };
int minimum_flips = minimumFlips(N, A, K);
System.out.println( minimum_flips);
}
}
// This code is contributed by hrithikgarg03188.
Python
# Python program to find Minimum flips to # Make mean of all k size # Sub-arrays less than 1 # Function to calculate # Minimum flips to make # Mean of all k size # Subarrays less than 1 def minimumFlips(N, A, K): # Initializing answer by 0 # That stores the number of flips answer = 0 # Initializing count variable by 0 # That stores the number of consecutive 1s count = 0 # iterating through the array for i in range(0, N): if (A[i] == 1): # If current element is 1, # We increment count by 1 count += 1 # if count of consecutive 1s # Reaches k, we increment the answer # as the mean of the subarray from # i-k to ith element becomes 1 if (count == K): answer += 1 count = 0 # else if current element is # 0, we make count 0 else: count = 0 # returning the required answer return answer # Driver Code N = 5 K = 5 A = [ 1, 1, 1, 1, 1 ] minimum_flips = minimumFlips(N, A, K) print(minimum_flips) # This code is contributed by Samim Hossain Mondal.
C#
// C# program to find Minimum flips to
// Make mean of all k size
// Sub-arrays less than 1
using System;
class GFG {
// Function to calculate
// Minimum flips to make
// Mean of all k size
// Subarrays less than 1
static int minimumFlips(int N, int[] A, int K)
{
// Initializing answer by 0
// That stores the number of flips
int answer = 0;
// Initializing count variable by 0
// That stores the number of consecutive 1s
int count = 0;
// iterating through the array
for (int i = 0; i < N; i++) {
if (A[i] == 1) {
// If current element is 1,
// We increment count by 1
count++;
// if count of consecutive 1s
// Reaches k, we increment the answer
// as the mean of the subarray from
// i-k to ith element becomes 1
if (count == K) {
answer++;
count = 0;
}
}
// else if current element is
// 0, we make count 0
else {
count = 0;
}
}
// returning the required answer
return answer;
}
// Driver Code
public static void Main(string[] args)
{
int N = 5, K = 5;
int[] A = { 1, 1, 1, 1, 1 };
int minimum_flips = minimumFlips(N, A, K);
Console.WriteLine(minimum_flips);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript code for the above approach
// Function to calculate
// Minimum flips to make
// Mean of all k size
// Subarrays less than 1
function minimumFlips(N, A, K)
{
// Initializing answer by 0
// That stores the number of flips
let answer = 0;
// Initializing count variable by 0
// That stores the number of consecutive 1s
let count = 0;
// iterating through the array
for (let i = 0; i < N; i++) {
if (A[i] == 1) {
// If current element is 1,
// We increment count by 1
count++;
// if count of consecutive 1s
// Reaches k, we increment the answer
// as the mean of the subarray from
// i-k to ith element becomes 1
if (count == K) {
answer++;
count = 0;
}
}
// else if current element is
// 0, we make count 0
else {
count = 0;
}
}
// returning the required answer
return answer;
}
// Driver Code
let N = 5, K = 5;
let A = [1, 1, 1, 1, 1];
let minimum_flips = minimumFlips(N, A, K);
document.write(minimum_flips);
// This code is contributed by Potta Lokesh
</script>
1
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA