Dada una array arr[] de tamaño N tal que cada elemento de la array sea -1, 0 o 1 , la tarea es verificar si es posible dividir la array en 3 subarreglos contiguos de modo que el producto del primero, segundo y tercer subarreglo es negativo, 0 y positivo respectivamente.
Ejemplos:
Entrada: arr[] = {-1, 0, 1}, N = 3
Salida: -1
0
1
Explicación: Divida la array en subarreglos {-1}, {0}, {1}.Entrada: arr[] = {1, -1, 1, -1}, N = 4
Salida: No es posible
Enfoque: el problema se puede resolver seleccionando con avidez los elementos hasta el primer ‘ -1 ‘ que no tiene 0′ como primer subarreglo y luego seleccionando los elementos desde el último hasta que el producto se convierte en 1 como el tercer subarreglo y los elementos restantes como el segundo subarreglo. Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos l y r como -1 , para almacenar el índice del último elemento del primer subarreglo y el primer elemento del tercer subarreglo.
- Recorra la array arr[] y si l es -1 y arr[i] es 0 , imprima “No es posible” . De lo contrario, si arr[i] es -1 , entonces asigne i a l y salga del bucle .
- Recorra la array arr[] en orden inverso y si el producto en el rango [i, N – 1] es mayor que 0 , entonces asigne i a r y salga del bucle .
- Compruebe si el valor l o r es -1 o l ≥ r o el recuento de 0 en el rango [l, r] es 0 . Si alguna de las condiciones es verdadera, imprima «No es posible» .
- Imprima el primer subarreglo sobre el rango [0, l] , el segundo subarreglo sobre el rango [l+1, r-1] y luego el último subarreglo sobre el rango [r, N-1] .
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 split an array into 3 contiguous // subarrays satisfying the given condition void PrintAllArrays(int arr[], int N) { // Store the index of rightmost // element of the first and leftmost // element of the third subarray int l = -1, r = -1; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If l is equal to -1 if (l == -1) { // If arr[i] is -1 if (arr[i] == -1) { l = i; break; } // If arr[i] is 0 if (arr[i] == 0) { cout << "Not Possible" << endl; return; } } } // Stores the product // of the last subarray int p = 1; // Traverse the array in reverse for (int i = N - 1; i >= 0; i--) { // Update the product p *= arr[i]; // If p is greater than 0, // assign i to r and break if (p > 0) { r = i; break; } } // If l or r is -1 or l to r, there // P are no 0's, print "Not possible" if (l == -1 || r == -1 || l >= r || count(arr + l, arr + r + 1, 0) == 0) { cout << "Not Possible" << endl; return; } // Print the three subarrays for (int i = 0; i <= l; i++) cout << arr[i] << " "; cout << "\n"; for (int i = l + 1; i < r; i++) cout << arr[i] << " "; cout << "\n"; for (int i = r; i < N; i++) cout << arr[i] << " "; } // Driver Code int main() { // Given Input int arr[] = { -1, 0, 1 }; int N = sizeof(arr) / sizeof(int); PrintAllArrays(arr, N); return 0; }
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Function to split an array into 3 contiguous // subarrays satisfying the given condition static void PrintAllArrays(int arr[], int N) { // Store the index of rightmost // element of the first and leftmost // element of the third subarray int l = -1, r = -1; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If l is equal to -1 if (l == -1) { // If arr[i] is -1 if (arr[i] == -1) { l = i; break; } // If arr[i] is 0 if (arr[i] == 0) { System.out.println("Not Possible"); return; } } } // Stores the product // of the last subarray int p = 1; // Traverse the array in reverse for(int i = N - 1; i >= 0; i--) { // Update the product p *= arr[i]; // If p is greater than 0, // assign i to r and break if (p > 0) { r = i; break; } } // If l or r is -1 or l to r, there // P are no 0's, print "Not possible" if (l == -1 || r == -1 || l >= r || count(arr, l, r + 1, 0) == 0) { System.out.println("Not Possible"); return; } // Print the three subarrays for(int i = 0; i <= l; i++) System.out.print(arr[i] + " "); System.out.println(); for(int i = l + 1; i < r; i++) System.out.print(arr[i] + " "); System.out.println(); for(int i = r; i < N; i++) System.out.print(arr[i] + " "); } // Function to return the number of occurrence of // the element 'val' in the range [start, end). static int count(int arr[], int start, int end, int val) { int count = 0; for(int i = start; i < end; i++) { if (arr[i] == val) { count++; } } return count; } // Driver Code public static void main(String[] args) { // Given Input int arr[] = { -1, 0, 1 }; int N = arr.length; PrintAllArrays(arr, N); } } // This code is contributed by Kingash
Python3
# Python3 program for the above approach # Function to split an array into 3 contiguous # subarrays satisfying the given condition def PrintAllArrays(arr, N): # Store the index of rightmost # element of the first and leftmost # element of the third subarray l = -1 r = -1 # Traverse the array arr[] for i in range(N): # If l is equal to -1 if (l == -1): # If arr[i] is -1 if (arr[i] == -1): l = i break # If arr[i] is 0 if (arr[i] == 0): print("Not Possible") return # Stores the product # of the last subarray p = 1 # Traverse the array in reverse for i in range(N - 1, -1, -1): # Update the product p *= arr[i] # If p is greater than 0, # assign i to r and break if (p > 0): r = i break # If l or r is -1 or l to r, there # P are no 0's, pr"Not possible" if (l == -1 or r == -1 or l >= r or count(arr, l, r + 1, 0) == 0): print("Not Possible") return # Printthe three subarrays for i in range(0, l + 1, 1): print(arr[i], end = " ") print() for i in range(l + 1, r, 1): print(arr[i], end = " ") print() for i in range(r, N, 1): print(arr[i], end = " ") # Function to return the number of occurrence of # the element 'val' in the range [start, end). def count(arr, start, end, val): count = 0 for i in range(start, end, 1): if (arr[i] == val): count += 1 return count # Driver Code # Given Input arr = [ -1, 0, 1 ] N = len(arr) PrintAllArrays(arr, N) # This code is contriobuted by code_hunt
C#
// C# program for the above approach using System; class GFG{ // Function to split an array into 3 contiguous // subarrays satisfying the given condition static void PrintAllArrays(int[] arr, int N) { // Store the index of rightmost // element of the first and leftmost // element of the third subarray int l = -1, r = -1; // Traverse the array arr[] for(int i = 0; i < N; i++) { // If l is equal to -1 if (l == -1) { // If arr[i] is -1 if (arr[i] == -1) { l = i; break; } // If arr[i] is 0 if (arr[i] == 0) { Console.WriteLine("Not Possible"); return; } } } // Stores the product // of the last subarray int p = 1; // Traverse the array in reverse for(int i = N - 1; i >= 0; i--) { // Update the product p *= arr[i]; // If p is greater than 0, // assign i to r and break if (p > 0) { r = i; break; } } // If l or r is -1 or l to r, there // P are no 0's, print "Not possible" if (l == -1 || r == -1 || l >= r || count(arr, l, r + 1, 0) == 0) { Console.WriteLine("Not Possible"); return; } // Print the three subarrays for(int i = 0; i <= l; i++) Console.Write(arr[i] + " "); Console.WriteLine(); for(int i = l + 1; i < r; i++) Console.Write(arr[i] + " "); Console.WriteLine(); for(int i = r; i < N; i++) Console.Write(arr[i] + " "); } // Function to return the number of occurrence of // the element 'val' in the range [start, end). static int count(int[] arr, int start, int end, int val) { int count = 0; for(int i = start; i < end; i++) { if (arr[i] == val) { count++; } } return count; } // Driver code public static void Main(String []args) { // Given Input int[] arr = { -1, 0, 1 }; int N = arr.Length; PrintAllArrays(arr, N); } } // This code is contributed by sanjoy_62
Javascript
<script> // JavaScript Program to implement // the above approach // Function to split an array into 3 contiguous // subarrays satisfying the given condition function PrintAllArrays(arr, N) { // Store the index of rightmost // element of the first and leftmost // element of the third subarray let l = -1, r = -1; // Traverse the array arr[] for(let i = 0; i < N; i++) { // If l is equal to -1 if (l == -1) { // If arr[i] is -1 if (arr[i] == -1) { l = i; break; } // If arr[i] is 0 if (arr[i] == 0) { document.write("Not Possible" + "<br/>"); return; } } } // Stores the product // of the last subarray let p = 1; // Traverse the array in reverse for(let i = N - 1; i >= 0; i--) { // Update the product p *= arr[i]; // If p is greater than 0, // assign i to r and break if (p > 0) { r = i; break; } } // If l or r is -1 or l to r, there // P are no 0's, print "Not possible" if (l == -1 || r == -1 || l >= r || count(arr, l, r + 1, 0) == 0) { document.write("Not Possible" + "<br/>"); return; } // Print the three subarrays for(let i = 0; i <= l; i++) document.write(arr[i] + " "); document.write("<br/>"); for(let i = l + 1; i < r; i++) document.write(arr[i] + " "); document.write("<br/>"); for(let i = r; i < N; i++) document.write(arr[i] + " "); } // Function to return the number of occurrence of // the element 'val' in the range [start, end). function count(arr, start, end, val) { let count = 0; for(let i = start; i < end; i++) { if (arr[i] == val) { count++; } } return count; } // Driver Code // Given Input let arr = [ -1, 0, 1 ]; let N = arr.length; PrintAllArrays(arr, N); </script>
-1 0 1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por hrithikgarg03188 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA