Dada una array binaria arr[] de N enteros, la tarea es encontrar el recuento máximo de subarreglos de distintos tamaños de modo que la suma de cada subarreglo sea K .
Ejemplo:
Entrada: arr[] = {0, 1, 1 , 0}, K = 2
Salida: 3
Explicación: El subconjunto {{0, 1, 1, 0}, {0, 1, 1}, {1, 1} } es el subconjunto de 3 subarreglos tales que la suma de cada subarreglo es 2 y el tamaño de cada subarreglo es distinto. El subarreglo {1, 1, 0} también tiene suma 2 pero ya se incluye un subarreglo de tamaño 3.Entrada: arr[] = {0, 1, 0, 0, 0, 1, 0}, K = 1
Salida: 5
Enfoque: El problema dado se puede resolver con la ayuda del algoritmo de ventana deslizante . Se puede observar que la suma de un subarreglo es igual a la cuenta de 1 en el subarreglo. A continuación se detallan los pasos a seguir:
- Mantenga una variable que realice un seguimiento del recuento de 1 en la ventana actual.
- Si el conteo de 1 en la ventana actual es menor que K , aumente el tamaño de la ventana y, de manera similar, si el conteo de 1 es mayor que K , reduzca el tamaño de la ventana.
- Para ventanas con suma K , inserte su tamaño en una estructura de datos establecida .
- El número de elementos en el conjunto después de atravesar la array completa es la respuesta requerida.
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 size of the largest
// subset of subarrays having given sum
// and size of each subarray is distinct
int maxSubsetSize(int arr[], int N, int K)
{
// Stores starting index
// of the current window
int ptr = 0;
// Stores distinct subarray
// sizes of the subset
unordered_set<int> s;
// Stores the sum of
// current window
int curSum = 0;
// Loop to traverse over array
for (int i = 0; i < N; i++) {
// Update current window sum
curSum += arr[i];
// If sum is less that K
if (curSum < K) {
continue;
}
// If sum is more than K
if (curSum > K) {
// Decrease window size
while (curSum > K) {
curSum -= arr[ptr++];
}
}
if (curSum == K) {
// Insert size of the
// current window
s.insert(i - ptr + 1);
int t = ptr;
// Iterate over all windows
// with same sum
while (arr[t] == 0) {
s.insert(i - t);
t++;
}
}
}
// Return Answer
return s.size();
}
// Driver Code
int main()
{
int arr[] = { 0, 1, 1, 0 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
cout << maxSubsetSize(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.HashSet;
class GFG {
// Function to find size of the largest
// subset of subarrays having given sum
// and size of each subarray is distinct
static int maxSubsetSize(int arr[], int N, int K) {
// Stores starting index
// of the current window
int ptr = 0;
// Stores distinct subarray
// sizes of the subset
HashSet<Integer> s = new HashSet<Integer>();
// Stores the sum of
// current window
int curSum = 0;
// Loop to traverse over array
for (int i = 0; i < N; i++) {
// Update current window sum
curSum += arr[i];
// If sum is less that K
if (curSum < K) {
continue;
}
// If sum is more than K
if (curSum > K) {
// Decrease window size
while (curSum > K) {
curSum -= arr[ptr++];
}
}
if (curSum == K) {
// Insert size of the
// current window
s.add(i - ptr + 1);
int t = ptr;
// Iterate over all windows
// with same sum
while (arr[t] == 0) {
s.add(i - t);
t++;
}
}
}
// Return Answer
return s.size();
}
// Driver Code
public static void main(String args[]) {
int arr[] = { 0, 1, 1, 0 };
int N = arr.length;
int K = 2;
System.out.println(maxSubsetSize(arr, N, K));
}
}
// This code is contributed by saurabh_jaiswal.
Python3
# python3 program for the above approach # Function to find size of the largest # subset of subarrays having given sum # and size of each subarray is distinct def maxSubsetSize(arr, N, K): # Stores starting index # of the current window ptr = 0 # Stores distinct subarray # sizes of the subset s = set() # Stores the sum of # current window curSum = 0 # Loop to traverse over array for i in range(0, N): # Update current window sum curSum += arr[i] # If sum is less that K if (curSum < K): continue # If sum is more than K if (curSum > K): # Decrease window size while (curSum > K): curSum -= arr[ptr] ptr += 1 if (curSum == K): # Insert size of the # current window s.add(i - ptr + 1) t = ptr # Iterate over all windows # with same sum while (arr[t] == 0): s.add(i - t) t += 1 # Return Answer return len(list(s)) # Driver Code if __name__ == "__main__": arr = [0, 1, 1, 0] N = len(arr) K = 2 print(maxSubsetSize(arr, N, K)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG {
// Function to find size of the largest
// subset of subarrays having given sum
// and size of each subarray is distinct
static int maxSubsetSize(int []arr, int N, int K)
{
// Stores starting index
// of the current window
int ptr = 0;
// Stores distinct subarray
// sizes of the subset
HashSet<int> s = new HashSet<int>();
// Stores the sum of
// current window
int curSum = 0;
// Loop to traverse over array
for (int i = 0; i < N; i++) {
// Update current window sum
curSum += arr[i];
// If sum is less that K
if (curSum < K) {
continue;
}
// If sum is more than K
if (curSum > K) {
// Decrease window size
while (curSum > K) {
curSum -= arr[ptr++];
}
}
if (curSum == K) {
// Insert size of the
// current window
s.Add(i - ptr + 1);
int t = ptr;
// Iterate over all windows
// with same sum
while (arr[t] == 0) {
s.Add(i - t);
t++;
}
}
}
// Return Answer
return s.Count;
}
// Driver Code
public static void Main(String []args) {
int []arr = { 0, 1, 1, 0 };
int N = arr.Length;
int K = 2;
Console.WriteLine(maxSubsetSize(arr, N, K));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code for the above approach
// Function to find size of the largest
// subset of subarrays having given sum
// and size of each subarray is distinct
function maxSubsetSize(arr, N, K) {
// Stores starting index
// of the current window
let ptr = 0;
// Stores distinct subarray
// sizes of the subset
let s = new Set();
// Stores the sum of
// current window
let curSum = 0;
// Loop to traverse over array
for (let i = 0; i < N; i++) {
// Update current window sum
curSum += arr[i];
// If sum is less that K
if (curSum < K) {
continue;
}
// If sum is more than K
if (curSum > K) {
// Decrease window size
while (curSum > K) {
curSum -= arr[ptr++];
}
}
if (curSum == K) {
// Insert size of the
// current window
s.add(i - ptr + 1);
let t = ptr;
// Iterate over all windows
// with same sum
while (arr[t] == 0) {
s.add(i - t);
t++;
}
}
}
// Return Answer
return s.size;
}
// Driver Code
let arr = [0, 1, 1, 0];
let N = arr.length;
let K = 2;
document.write(maxSubsetSize(arr, N, K));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por abhishek1110 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA