Dado un arreglo que contiene solo 0 y 1, encuentre el subarreglo más grande que contenga el mismo número de 0 y 1. La complejidad temporal esperada es O(n).
Ejemplos:
Input: arr[] = {1, 0, 1, 1, 1, 0, 0} Output: 1 to 6 (Starting and Ending indexes of output subarray) Input: arr[] = {1, 1, 1, 1} Output: No such subarray Input: arr[] = {0, 0, 1, 1, 0} Output: 0 to 3 Or 1 to 4
Método 1 : Fuerza bruta.
Enfoque: El enfoque de fuerza bruta en este tipo de preguntas es generar todos los sub-arreglos posibles. Luego, en primer lugar, verifique si el subarreglo tiene el mismo número de 0 y 1 o no. Para facilitar este proceso, tome la suma acumulativa de los subconjuntos tomando 0 como -1 y 1 como está. El punto donde la suma acumulativa = 0 significará que el subarreglo desde el inicio hasta ese punto tiene el mismo número de 0 y 1 . Ahora que este es un subconjunto válido, compare su tamaño con el tamaño máximo de dicho subconjunto encontrado hasta ahora.
Algoritmo:
- Utilice un puntero inicial que signifique el punto inicial del subarreglo.
- Tome una variable sum=0 que tomará la suma acumulada de todos los elementos del subconjunto.
- Inicialícelo con el valor 1 si el valor en el punto de inicio = 1 , de lo contrario, inicialícelo con -1 .
- Ahora inicie un ciclo interno y comience a tomar la suma acumulada de elementos siguiendo la misma lógica.
- Si la suma acumulativa (valor de la suma) = 0 , significa que el subarreglo tiene el mismo número de 0 y 1 .
- Ahora compare su tamaño con el tamaño del subconjunto más grande, si es mayor, almacene el primer índice de dicho subconjunto en una variable y actualice el valor del tamaño.
- Imprima el subarreglo con el índice inicial y el tamaño devuelto por el algoritmo anterior.
Pseudocódigo:
Run a loop from i=0 to n-2 if(arr[i]==1) sum=1 else sum=-1 Run inner loop from j=i+1 to n-1 sum+=arr[j] if(sum==0) if(j-i+1>max_size) start_index=i max_size=j-i+1 Run a loop from i=start_index till max_size-1 print(arr[i])
C++
// A simple C++ program to find the largest // subarray with equal number of 0s and 1s #include <bits/stdc++.h> using namespace std; // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. int findSubArray(int arr[], int n) { int sum = 0; int maxsize = -1, startindex; // Pick a starting point as i for (int i = 0; i < n - 1; i++) { sum = (arr[i] == 0) ? -1 : 1; // Consider all subarrays starting from i for (int j = i + 1; j < n; j++) { (arr[j] == 0) ? (sum += -1) : (sum += 1); // If this is a 0 sum subarray, then // compare it with maximum size subarray // calculated so far if (sum == 0 && maxsize < j - i + 1) { maxsize = j - i + 1; startindex = i; } } } if (maxsize == -1) cout << "No such subarray"; else cout << startindex << " to " << startindex + maxsize - 1; return maxsize; } /* Driver code*/ int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int size = sizeof(arr) / sizeof(arr[0]); findSubArray(arr, size); return 0; } // This code is contributed by rathbhupendra
C
// A simple program to find the largest subarray // with equal number of 0s and 1s #include <stdio.h> // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. int findSubArray(int arr[], int n) { int sum = 0; int maxsize = -1, startindex; // Pick a starting point as i for (int i = 0; i < n - 1; i++) { sum = (arr[i] == 0) ? -1 : 1; // Consider all subarrays starting from i for (int j = i + 1; j < n; j++) { (arr[j] == 0) ? (sum += -1) : (sum += 1); // If this is a 0 sum subarray, then // compare it with maximum size subarray // calculated so far if (sum == 0 && maxsize < j - i + 1) { maxsize = j - i + 1; startindex = i; } } } if (maxsize == -1) printf("No such subarray"); else printf("%d to %d", startindex, startindex + maxsize - 1); return maxsize; } /* Driver program to test above functions*/ int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int size = sizeof(arr) / sizeof(arr[0]); findSubArray(arr, size); return 0; }
Java
class LargestSubArray { // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. int findSubArray(int arr[], int n) { int sum = 0; int maxsize = -1, startindex = 0; int endindex = 0; // Pick a starting point as i for (int i = 0; i < n - 1; i++) { sum = (arr[i] == 0) ? -1 : 1; // Consider all subarrays starting from i for (int j = i + 1; j < n; j++) { if (arr[j] == 0) sum += -1; else sum += 1; // If this is a 0 sum subarray, then // compare it with maximum size subarray // calculated so far if (sum == 0 && maxsize < j - i + 1) { maxsize = j - i + 1; startindex = i; } } } endindex = startindex + maxsize - 1; if (maxsize == -1) System.out.println("No such subarray"); else System.out.println(startindex + " to " + endindex); return maxsize; } /* Driver program to test the above functions */ public static void main(String[] args) { LargestSubArray sub; sub = new LargestSubArray(); int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int size = arr.length; sub.findSubArray(arr, size); } }
Python3
# A simple program to find the largest subarray # with equal number of 0s and 1s # This function Prints the starting and ending # indexes of the largest subarray with equal # number of 0s and 1s. Also returns the size # of such subarray. def findSubArray(arr, n): sum = 0 maxsize = -1 # Pick a starting point as i for i in range(0, n-1): sum = -1 if(arr[i] == 0) else 1 # Consider all subarrays starting from i for j in range(i + 1, n): sum = sum + (-1) if (arr[j] == 0) else sum + 1 # If this is a 0 sum subarray, then # compare it with maximum size subarray # calculated so far if (sum == 0 and maxsize < j-i + 1): maxsize = j - i + 1 startindex = i if (maxsize == -1): print("No such subarray"); else: print(startindex, "to", startindex + maxsize-1); return maxsize # Driver program to test above functions arr = [1, 0, 0, 1, 0, 1, 1] size = len(arr) findSubArray(arr, size) # This code is contributed by Smitha Dinesh Semwal
C#
// A simple program to find the largest subarray // with equal number of 0s and 1s using System; class GFG { // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. static int findSubArray(int[] arr, int n) { int sum = 0; int maxsize = -1, startindex = 0; int endindex = 0; // Pick a starting point as i for (int i = 0; i < n - 1; i++) { sum = (arr[i] == 0) ? -1 : 1; // Consider all subarrays starting from i for (int j = i + 1; j < n; j++) { if (arr[j] == 0) sum += -1; else sum += 1; // If this is a 0 sum subarray, then // compare it with maximum size subarray // calculated so far if (sum == 0 && maxsize < j - i + 1) { maxsize = j - i + 1; startindex = i; } } } endindex = startindex + maxsize - 1; if (maxsize == -1) Console.WriteLine("No such subarray"); else Console.WriteLine(startindex + " to " + endindex); return maxsize; } // Driver program public static void Main() { int[] arr = { 1, 0, 0, 1, 0, 1, 1 }; int size = arr.Length; findSubArray(arr, size); } } // This code is contributed by Sam007
PHP
<?php // A simple program to find the // largest subarray with equal // number of 0s and 1s // This function Prints the starting // and ending indexes of the largest // subarray with equal number of 0s // and 1s. Also returns the size of // such subarray. function findSubArray(&$arr, $n) { $sum = 0; $maxsize = -1; // Pick a starting point as i for ($i = 0; $i < $n - 1; $i++) { $sum = ($arr[$i] == 0) ? -1 : 1; // Consider all subarrays // starting from i for ($j = $i + 1; $j < $n; $j++) { ($arr[$j] == 0) ? ($sum += -1) : ($sum += 1); // If this is a 0 sum subarray, // then compare it with maximum // size subarray calculated so far if ($sum == 0 && $maxsize < $j - $i + 1) { $maxsize = $j - $i + 1; $startindex = $i; } } } if ($maxsize == -1) echo "No such subarray"; else echo $startindex. " to " . ($startindex + $maxsize - 1); return $maxsize; } // Driver Code $arr = array(1, 0, 0, 1, 0, 1, 1); $size = sizeof($arr); findSubArray($arr, $size); // This code is contributed // by ChitraNayal ?>
Javascript
<script> // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. function findSubArray(arr,n) { let sum = 0; let maxsize = -1, startindex = 0; let endindex = 0; // Pick a starting point as i for (let i = 0; i < n - 1; i++) { sum = (arr[i] == 0) ? -1 : 1; // Consider all subarrays starting from i for (let j = i + 1; j < n; j++) { if (arr[j] == 0) sum += -1; else sum += 1; // If this is a 0 sum subarray, then // compare it with maximum size subarray // calculated so far if (sum == 0 && maxsize < j - i + 1) { maxsize = j - i + 1; startindex = i; } } } endindex = startindex + maxsize - 1; if (maxsize == -1) document.write("No such subarray"); else document.write(startindex + " to " + endindex); return maxsize; } /* Driver program to test the above functions */ let arr=[1, 0, 0, 1, 0, 1, 1]; let size = arr.length; findSubArray(arr, size); // This code is contributed by avanitrachhadiya2155 </script>
Producción:
0 to 5
Análisis de Complejidad:
- Complejidad de tiempo: O(n^2).
Como todos los subconjuntos posibles se generan utilizando un par de bucles anidados. - Espacio Auxiliar: O(1).
Como no se utiliza una estructura de datos adicional que ocupe espacio auxiliar.
Método 2: Hashmap .
Enfoque: El concepto de tomar una suma acumulativa, tomar 0 como -1 nos ayudará a optimizar el enfoque. Al tomar la suma acumulativa, hay dos casos en los que puede haber una subarray con el mismo número de 0 y 1.
- Cuando la suma acumulativa = 0 , lo que significa que la subarray desde el índice (0) hasta el índice actual tiene el mismo número de 0 y 1 .
- Cuando encontramos un valor de suma acumulativa que ya hemos encontrado antes, lo que significa que la subarray desde el índice anterior + 1 hasta el índice actual tiene el mismo número de 0 y 1, ya que dan una suma acumulativa de 0 .
En pocas palabras, este problema es equivalente a encontrar dos índices i & j en array[] tal que array[i] = array[j] y (ji) sea máximo . Para almacenar la primera aparición de cada valor de suma acumulativa único, usamos un hash_map en el que, si obtenemos ese valor nuevamente, podemos encontrar el tamaño del subconjunto y compararlo con el tamaño máximo encontrado hasta ahora.
Algoritmo:
- Deje que la array de entrada sea arr[] de tamaño n y max_size sea el tamaño de la sub-array de salida.
- Cree una array temporal sumleft[] de tamaño n. Almacene la suma de todos los elementos desde arr[0] hasta arr[i] en sumleft[i].
- Hay dos casos, el subarreglo de salida puede comenzar desde el índice 0 o puede comenzar desde algún otro índice. Devolveremos el máximo de los valores obtenidos por dos casos.
- Para encontrar la subarray de longitud máxima a partir del índice 0, escanee sumleft[] y encuentre la i máxima donde sumleft[i] = 0.
- Ahora, necesitamos encontrar el subarreglo donde la suma del subarreglo es 0 y el índice de inicio no es 0. Este problema es equivalente a encontrar dos índices i & j en sumleft[] tal que sumleft[i] = sumleft[j] y ji es máximo . Para resolver esto, creamos una tabla hash con tamaño = max-min+1 donde min es el valor mínimo en sumleft[] y max es el valor máximo en sumleft[]. Hash las ocurrencias más a la izquierda de todos los valores diferentes en sumleft[]. El tamaño del hash se elige como max-min+1 porque puede haber muchos valores diferentes posibles en sumleft[]. Inicialice todos los valores en hash como -1.
- Para llenar y usar hash[], recorra sumleft[] de 0 a n-1. Si un valor no está presente en hash[], almacene su índice en hash. Si el valor está presente, calcule la diferencia del índice actual de sumleft[] y el valor previamente almacenado en hash[]. Si esta diferencia es mayor que el tamaño máximo, actualice el tamaño máximo.
- Para manejar casos de esquina (todos los 1 y todos los 0), inicializamos maxsize como -1. Si el tamaño máximo sigue siendo -1, imprima que no existe tal subarreglo.
Pseudocódigo:
int sum_left[n] Run a loop from i=0 to n-1 if(arr[i]==0) sumleft[i] = sumleft[i-1]+-1 else sumleft[i] = sumleft[i-1]+ 1 if (sumleft[i] > max) max = sumleft[i]; Run a loop from i=0 to n-1 if (sumleft[i] == 0) { maxsize = i+1; startindex = 0; } // Case 2: fill hash table value. If already then use it if (hash[sumleft[i]-min] == -1) hash[sumleft[i]-min] = i; else { if ((i - hash[sumleft[i]-min]) > maxsize) { maxsize = i - hash[sumleft[i]-min]; startindex = hash[sumleft[i]-min] + 1; } } return maxsize
C++
// C++ program to find largest subarray with equal number of // 0's and 1's. #include <bits/stdc++.h> using namespace std; // Returns largest subarray with equal number of 0s and 1s int maxLen(int arr[], int n) { // Creates an empty hashMap hM unordered_map<int, int> hM; int sum = 0; // Initialize sum of elements int max_len = 0; // Initialize result int ending_index = -1; for (int i = 0; i < n; i++) arr[i] = (arr[i] == 0) ? -1 : 1; // Traverse through the given array for (int i = 0; i < n; i++) { // Add current element to sum sum += arr[i]; // To handle sum=0 at last index if (sum == 0) { max_len = i + 1; ending_index = i; } // If this sum is seen before, then update max_len // if required if (hM.find(sum) != hM.end()) { if (max_len < i - hM[sum]) { max_len = i - hM[sum]; ending_index = i; } } else // Else put this sum in hash table hM[sum] = i; } for (int i = 0; i < n; i++) arr[i] = (arr[i] == -1) ? 0 : 1; printf("%d to %d\n", ending_index - max_len + 1, ending_index); return max_len; } // Driver method int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int n = sizeof(arr) / sizeof(arr[0]); maxLen(arr, n); return 0; } // This code is contributed by Aditya Goel
C
// A O(n) program to find the largest subarray // with equal number of 0s and 1s #include <stdio.h> #include <stdlib.h> // A utility function to get maximum of two // integers int max(int a, int b) { return a > b ? a : b; } // This function Prints the starting and ending // indexes of the largest subarray with equal // number of 0s and 1s. Also returns the size // of such subarray. int findSubArray(int arr[], int n) { // variables to store result values int maxsize = -1, startindex; // Create an auxiliary array sunmleft[]. // sumleft[i] will be sum of array // elements from arr[0] to arr[i] int sumleft[n]; // For min and max values in sumleft[] int min, max; int i; // Fill sumleft array and get min and max // values in it. Consider 0 values in arr[] // as -1 sumleft[0] = ((arr[0] == 0) ? -1 : 1); min = arr[0]; max = arr[0]; for (i = 1; i < n; i++) { sumleft[i] = sumleft[i - 1] + ((arr[i] == 0) ? -1 : 1); if (sumleft[i] < min) min = sumleft[i]; if (sumleft[i] > max) max = sumleft[i]; } // Now calculate the max value of j - i such // that sumleft[i] = sumleft[j]. The idea is // to create a hash table to store indexes of all // visited values. // If you see a value again, that it is a case of // sumleft[i] = sumleft[j]. Check if this j-i is // more than maxsize. // The optimum size of hash will be max-min+1 as // these many different values of sumleft[i] are // possible. Since we use optimum size, we need // to shift all values in sumleft[] by min before // using them as an index in hash[]. int hash[max - min + 1]; // Initialize hash table for (i = 0; i < max - min + 1; i++) hash[i] = -1; for (i = 0; i < n; i++) { // Case 1: when the subarray starts from // index 0 if (sumleft[i] == 0) { maxsize = i + 1; startindex = 0; } // Case 2: fill hash table value. If already // filled, then use it if (hash[sumleft[i] - min] == -1) hash[sumleft[i] - min] = i; else { if ((i - hash[sumleft[i] - min]) > maxsize) { maxsize = i - hash[sumleft[i] - min]; startindex = hash[sumleft[i] - min] + 1; } } } if (maxsize == -1) printf("No such subarray"); else printf("%d to %d", startindex, startindex + maxsize - 1); return maxsize; } /* Driver program to test above functions */ int main() { int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int size = sizeof(arr) / sizeof(arr[0]); findSubArray(arr, size); return 0; }
Java
import java.util.HashMap; class LargestSubArray1 { // Returns largest subarray with // equal number of 0s and 1s int maxLen(int arr[], int n) { // Creates an empty hashMap hM HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); // Initialize sum of elements int sum = 0; // Initialize result int max_len = 0; int ending_index = -1; int start_index = 0; for (int i = 0; i < n; i++) { arr[i] = (arr[i] == 0) ? -1 : 1; } // Traverse through the given array for (int i = 0; i < n; i++) { // Add current element to sum sum += arr[i]; // To handle sum=0 at last index if (sum == 0) { max_len = i + 1; ending_index = i; } // If this sum is seen before, // then update max_len if required if (hM.containsKey(sum)) { if (max_len < i - hM.get(sum)) { max_len = i - hM.get(sum); ending_index = i; } } else // Else put this sum in hash table hM.put(sum, i); } for (int i = 0; i < n; i++) { arr[i] = (arr[i] == -1) ? 0 : 1; } int end = ending_index - max_len + 1; System.out.println(end + " to " + ending_index); return max_len; } /* Driver program to test the above functions */ public static void main(String[] args) { LargestSubArray1 sub = new LargestSubArray1(); int arr[] = { 1, 0, 0, 1, 0, 1, 1 }; int n = arr.length; sub.maxLen(arr, n); } } // This code has been by Mayank Jaiswal(mayank_24)
Python3
# Python 3 program to find largest # subarray with equal number of # 0's and 1's. # Returns largest subarray with # equal number of 0s and 1s def maxLen(arr, n): # NOTE: Dictionary in python in # implemented as Hash Maps. # Create an empty hash map (dictionary) hash_map = {} curr_sum = 0 max_len = 0 ending_index = -1 for i in range (0, n): if(arr[i] == 0): arr[i] = -1 else: arr[i] = 1 # Traverse through the given array for i in range (0, n): # Add current element to sum curr_sum = curr_sum + arr[i] # To handle sum = 0 at last index if (curr_sum == 0): max_len = i + 1 ending_index = i # If this sum is seen before, if curr_sum in hash_map: # If max_len is smaller than new subarray # Update max_len and ending_index if max_len < i - hash_map[curr_sum]: max_len = i - hash_map[curr_sum] ending_index = i else: # else put this sum in dictionary hash_map[curr_sum] = i for i in range (0, n): if(arr[i] == -1): arr[i] = 0 else: arr[i] = 1 print (ending_index - max_len + 1, end =" ") print ("to", end = " ") print (ending_index) return max_len # Driver Code arr = [1, 0, 0, 1, 0, 1, 1] n = len(arr) maxLen(arr, n) # This code is contributed # by Tarun Garg
C#
// C# program to find the largest subarray // with equal number of 0s and 1s using System; using System.Collections.Generic; class LargestSubArray1 { // Returns largest subarray with // equal number of 0s and 1s public virtual int maxLen(int[] arr, int n) { // Creates an empty Dictionary hM Dictionary<int, int> hM = new Dictionary<int, int>(); int sum = 0; // Initialize sum of elements int max_len = 0; // Initialize result int ending_index = -1; int start_index = 0; for (int i = 0; i < n; i++) { arr[i] = (arr[i] == 0) ? -1 : 1; } // Traverse through the given array for (int i = 0; i < n; i++) { // Add current element to sum sum += arr[i]; // To handle sum=0 at last index if (sum == 0) { max_len = i + 1; ending_index = i; } // If this sum is seen before, // then update max_len // if required if (hM.ContainsKey(sum)) { if (max_len < i - hM[sum]) { max_len = i - hM[sum]; ending_index = i; } } else // Else put this sum in hash table { hM[sum] = i; } } for (int i = 0; i < n; i++) { arr[i] = (arr[i] == -1) ? 0 : 1; } int end = ending_index - max_len + 1; Console.WriteLine(end + " to " + ending_index); return max_len; } // Driver Code public static void Main(string[] args) { LargestSubArray1 sub = new LargestSubArray1(); int[] arr = new int[] { 1, 0, 0, 1, 0, 1, 1 }; int n = arr.Length; sub.maxLen(arr, n); } } // This code is contributed by Shrikant13
Javascript
<script> // Javascript program to find largest // subarray with equal number of // 0's and 1's. // Returns largest subarray with equal // number of 0s and 1s function maxLen(arr, n) { // Creates an empty hashMap hM let hM = new Map(); // Initialize sum of elements let sum = 0; // Initialize result let max_len = 0; let ending_index = -1; for(let i = 0; i < n; i++) arr[i] = (arr[i] == 0) ? -1 : 1; // Traverse through the given array for(let i = 0; i < n; i++) { // Add current element to sum sum += arr[i]; // To handle sum=0 at last index if (sum == 0) { max_len = i + 1; ending_index = i; } // If this sum is seen before, then // update max_len if required if (hM.has(sum)) { if (max_len < i - hM[sum]) { max_len = i - hM[sum]; ending_index = i; } } // Else put this sum in hash table else hM[sum] = i; } for(let i = 0; i < n; i++) arr[i] = (arr[i] == -1) ? 0 : 1; document.write(ending_index - max_len + 1 + " to " + ending_index); return max_len; } // Driver code let arr = [ 1, 0, 0, 1, 0, 1, 1 ]; let n = arr.length; maxLen(arr, n); // This code is contributed by gfgking </script>
Producción:
0 to 5
Análisis de Complejidad:
- Complejidad temporal: O(n).
Como la array dada se recorre una sola vez. - Espacio Auxiliar: O(n).
Como se ha utilizado hash_map , que ocupa espacio adicional.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA