Cuente las formas de particionar Binary Array en subarreglos que contengan K 0 cada uno

Dada una array binaria arr[] de tamaño N y un número entero K , la tarea es calcular el número de formas de dividir la array en subarreglos que no se superponen, donde cada subarreglo tiene exactamente K números 0.

Ejemplos:

Entrada: arr[] = [ 0, 0, 1, 1, 0, 1, 0], K = 2
Salida: 3
Explicación: Las diferentes particiones posibles son: 
{{0, 0}, {1, 1, 0, 1 , 0}}, {{0, 0, 1}, {1, 0, 1, 0}}, {{0, 0, 1, 1}, {0, 1, 0}}. Entonces, la salida será 3.

Entrada: arr[] = {0, 0, 1, 0, 1, 0}, K = 2
Salida: 2

Entrada: arr[] = [1, 0, 1, 1], K = 2
Salida: 0

Enfoque: El enfoque para resolver el problema se basa en la siguiente idea:

Si j-ésimo 0 es el último 0 para un subarreglo y (j+1)-ésimo 0 es el primer 0 de otro subarreglo, entonces el número posible de formas de dividir esos dos subarreglos es uno más que el número de 1 entre j-ésimo y (j+1)th 0.

De la observación anterior, se puede decir que el total de formas posibles de dividir el subarreglo es la multiplicación de la cuenta de 1s entre K*xth y (K*x + 1)th 0, para todos los x posibles tales que K* x no excede el recuento total de 0 en la array.

Siga la ilustración a continuación para una mejor comprensión del problema,

Ilustración:

Considere la array arr[] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0} , K = 2

El índice del 2° 0 y el 3° 0 es 1 y 4
        => Número total de 1 entre ellos = 2.
        => Partición posible con estos 0 = 2 + 1 = 3.
        => Total de particiones posibles hasta ahora = 3

El índice del 4.º 0 y el 5.º 0 son 6 y 8
        => Número total de 1 entre ellos = 1.
        => Posible partición con estos 0 = 1 + 1 = 2.
        => Total de particiones posibles hasta ahora = 3*2 = 6

Las posibles particiones son 6 : 
{{0, 0}, {1, 1, 0, 1, 0}, {1, 0, 0}}, {{0, 0}, {1, 1, 0, 1, 0, 1}, {0, 0}},  
{{0, 0, 1}, {1, 0, 1, 0}, {1, 0, 0}}, {{0, 0, 1}, { 1, 0, 1, 0, 1}, {0, 0}}, 
{{0, 0, 1, 1}, {0, 1, 0}, {1, 0, 0}}, {{0, 0, 1, 1}, {0, 1, 0, 1}, {0, 0}} 

Siga los pasos que se mencionan a continuación para resolver el problema:

• Inicialice una variable de contador a 1 (afirmando que existe al menos una de esas formas posibles). 
• Si hay menos de K 0 o el número de 0 no es divisible por K , entonces dicha partición no es posible.
• Luego, para cada número posible (K*x)th y (K*x + 1)th de 0, calcule el número de particiones posibles utilizando la observación anterior y multiplíquelo con la variable contador para obtener el total de particiones posibles.
• Devuelve el valor de la variable contador.

Aquí está el código para el enfoque anterior:

// C++ program for above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function used to calculate the number of
// ways to divide the array
int number_of_ways(vector<int>& arr, int K)
{
    // Initialize a counter variable no_0 to
    // calculate the number of 0
    int no_0 = 0;
 
    // Initialize a vector to
    // store the indices of 0s
    vector<int> zeros;
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == 0) {
            no_0++;
            zeros.push_back(i);
        }
    }
 
    // If number of 0 is not divisible by K
    // or no 0 in the sequence return 0
    if (no_0 % K || no_0 == 0)
        return 0;
 
    int res = 1;
 
    // For every (K*n)th and (K*n+1)th 0
    // calculate the distance between them
    for (int i = K; i < zeros.size();) {
        res *= (zeros[i] - zeros[i - 1]);
        i += K;
    }
 
    // Return the number of such partitions
    return res;
}
 
// Driver code
int main()
{
    vector<int> arr = { 0, 0, 1, 1, 0, 1, 0 };
    int K = 2;
 
    // Function call
    cout << number_of_ways(arr, K) << endl;
    return 0;
}

// Java program for above approach
import java.io.*;
import java.util.*;
 
class GFG {
    // Function used to calculate the number of
    // ways to divide the array
    public static int number_of_ways(int arr[], int K)
    {
        // Initialize a counter variable no_0 to
        // calculate the number of 0
        int no_0 = 0;
 
        // Initialize a arraylist to
        // store the indices of 0s
        ArrayList<Integer> zeros = new ArrayList<Integer>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                no_0++;
                zeros.add(i);
            }
        }
 
        // If number of 0 is not divisible by K
        // or no 0 in the sequence return 0
        if ((no_0 % K != 0) || no_0 == 0)
            return 0;
 
        int res = 1;
 
        // For every (K*n)th and (K*n+1)th 0
        // calculate the distance between them
        for (int i = K; i < zeros.size();) {
            res *= (zeros.get(i) - zeros.get(i - 1));
            i += K;
        }
 
        // Return the number of such partitions
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int arr[] = { 0, 0, 1, 1, 0, 1, 0 };
        int K = 2;
 
        // Function call
        System.out.println(number_of_ways(arr, K));
    }
}
 
// This code is contributed by Rohit Pradhan

# Python3 program for above approach
 
# Function used to calculate the number of
# ways to divide the array
def number_of_ways(arr, K):
   
    # Initialize a counter variable no_0 to
    # calculate the number of 0
    no_0 = 0
     
    # Initialize am array to
    # store the indices of 0s
    zeros = []
    for i in range(len(arr)):
        if arr[i] == 0:
            no_0 += 1
            zeros.append(i)
             
    # If number of 0 is not divisible by K
    # or no 0 in the sequence return 0
    if no_0 % K or no_0 == 0:
        return 0
 
    res = 1
     
    # For every (K*n)th and (K*n+1)th 0
    # calculate the distance between them
    i = K
    while (i < len(zeros)):
        res *= (zeros[i] - zeros[i - 1])
        i += K
         
    # Return the number of such partitions
    return res
 
# Driver code
arr = [0, 0, 1, 1, 0, 1, 0]
K = 2
 
# Function call
print(number_of_ways(arr, K))
 
# This code is contributed by phasing17.

// C# program for above approach
 
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function used to calculate the number of
  // ways to divide the array
  public static int number_of_ways(int[] arr, int K)
  {
 
    // Initialize a counter variable no_0 to
    // calculate the number of 0
    int no_0 = 0;
 
    // Initialize a arraylist to
    // store the indices of 0s
    var zeros = new List<int>();
    for (int i = 0; i < arr.Length; i++) {
      if (arr[i] == 0) {
        no_0++;
        zeros.Add(i);
      }
    }
 
    // If number of 0 is not divisible by K
    // or no 0 in the sequence return 0
    if ((no_0 % K != 0) || no_0 == 0)
      return 0;
 
    int res = 1;
 
    // For every (K*n)th and (K*n+1)th 0
    // calculate the distance between them
    for (int i = K; i < zeros.Count;) {
      res *= (zeros[i] - zeros[i - 1]);
      i += K;
    }
 
    // Return the number of such partitions
    return res;
  }
  public static void Main(string[] args)
  {
    int[] arr = { 0, 0, 1, 1, 0, 1, 0 };
    int K = 2;
 
    // Function call
    Console.WriteLine(number_of_ways(arr, K));
  }
}
 
// this code was contributed by phasing17

<script>
    // JavaScript program for above approach
 
 
    // Function used to calculate the number of
    // ways to divide the array
    const number_of_ways = (arr, K) => {
        // Initialize a counter variable no_0 to
        // calculate the number of 0
        let no_0 = 0;
 
        // Initialize a vector to
        // store the indices of 0s
        let zeros = [];
        for (let i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                no_0++;
                zeros.push(i);
            }
        }
 
        // If number of 0 is not divisible by K
        // or no 0 in the sequence return 0
        if (no_0 % K || no_0 == 0)
            return 0;
 
        let res = 1;
 
        // For every (K*n)th and (K*n+1)th 0
        // calculate the distance between them
        for (let i = K; i < zeros.length;) {
            res *= (zeros[i] - zeros[i - 1]);
            i += K;
        }
 
        // Return the number of such partitions
        return res;
    }
 
    // Driver code
 
    let arr = [0, 0, 1, 1, 0, 1, 0];
    let K = 2;
 
    // Function call
    document.write(number_of_ways(arr, K));
 
// This code is contributed by rakeshsahni
 
</script>

3

Complejidad temporal: O(N)
Espacio auxiliar: O(N)