Given an array arr[] size N such that each array element is either -1, 0, or 1, the task is to check if is it possible to split the array into 3 contiguous subarrays such that the product of the first, second and third subarrays is negative, 0 and positive respectively.
Examples:
Input: arr[] = {-1, 0, 1}, N = 3
Output: -1
0
1
Explanation: Split the array into subarrays {-1}, {0}, {1}.Input: arr[] = {1, -1, 1, -1}, N = 4
Output: Not Possible
Approach: The problem can be solved by greedily selecting the elements up to first ‘-1‘ having no 0′s as the first subarray and then selecting the elements from the last until the product becomes 1 as the third subarray and the remaining elements as the second subarray. Follow the steps below to solve the problem:
- Initialize two variables, say l and r as -1, to store the index of the last element of the first subarray and the first element of the third subarray.
- Traverse the array arr[] and if l is -1 and arr[i] is 0, then print “Not possible”. Otherwise, if arr[i] is -1, then assign i to l and break out of the loop.
- Traverse the array arr[] in reverse order and if the product in the range [i, N – 1] is greater than 0, then assign i to r and break out of the loop.
- Check if the value l or r is -1 or l ≥ r or count of 0s in the range [l, r] is 0. If any of the condition is true, print “Not Possible”.
- Print the first subarray over the range [0, l], the second subarray over the range [l+1, r-1], and then the last subarray over the range [r, N-1].
Below is the implementation of the above approach:
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 conditionvoid 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 Codeint 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 approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to split an array into 3 contiguous// subarrays satisfying the given conditionstatic 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 Codepublic 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 conditiondef 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 Inputarr = [ -1, 0, 1 ]N = len(arr)PrintAllArrays(arr, N) # This code is contriobuted by code_hunt |
C#
// C# program for the above approachusing System;class GFG{ // Function to split an array into 3 contiguous// subarrays satisfying the given conditionstatic 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 codepublic 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 conditionfunction 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> |
Output:
-1 0 1
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
