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>
Producción:
-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