Count ways to split Array such that sum of max of left and min of right is at least K
Given an array A[] consisting of N integers and an integer K. The task is to find the total number of ways in which you can divide the array into two parts such that the sum of the largest element in the left part and the smallest element in the right part is greater than or equal to K.
Examples:
Input: A[] = {1, 2, 3}, N = 3, K = 3
Output: 2
Explanation:
Two ways in which array is divided to satisfy above conditions are:
{1} and {2, 3} -> 1+2>=3(satisfies the condition)
{1, 2} and {3} -> 2+3>=3(satisfies the condition)Input: A[] = {1, 2, 3, 4, 5}, N = 5, K = 5
Output: 3
Explanation:
{1, 2} and {3, 4, 5} -> 2+3>=5
{1, 2, 3} and {4, 5} -> 3+4>=5
{1, 2, 3, 4} and {5} -> 4+5>=5
Approach:
Use the following idea to solve the given problem:
Prefix array of the maximum element for the left and suffix array of the minimum element for the right can give the maximum and minimum element in constant time
Follow the below steps to solve the given problem:
- Create two arrays left and right .
- left[] array is used to store the maximum elements from 0 to i.
- right[] array is used to store the minimum elements from i to N-1.
- Traverse the given array and check if left[i] + right[i+1] ? K. If the condition is satisfied, Increment the answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the number of ways int totalCuts( int N, int K, vector< int >& A) { // Arrays to store the prefix max and // suffix min for the current position vector< int > left(N), right(N); left[0] = A[0]; right[N - 1] = A[N - 1]; // Calculating the prefix maximum for ( int i = 1; i < N; i++) left[i] = max(A[i], left[i - 1]); // Calculating the suffix minimum for ( int i = N - 2; i >= 0; i--) right[i] = min(A[i], right[i + 1]); // Initialize the answer int ans = 0; for ( int i = 0; i < N - 1; i++) // If sum is greater or equal to K if (left[i] + right[i + 1] >= K) ans++; return ans; } // Driver Code int main() { int K = 5; vector< int > A = { 1, 2, 3, 4, 5 }; int N = A.size(); // Function Call cout << totalCuts(N, K, A); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the number of ways static int totalCuts( int N, int K, int []A) { // Arrays to store the prefix max and // suffix min for the current position int [] left = new int [N]; int [] right = new int [N]; left[ 0 ] = A[ 0 ]; right[N - 1 ] = A[N - 1 ]; // Calculating the prefix maximum for ( int i = 1 ; i < N; i++) left[i] = Math.max(A[i], left[i - 1 ]); // Calculating the suffix minimum for ( int i = N - 2 ; i >= 0 ; i--) right[i] = Math.min(A[i], right[i + 1 ]); // Initialize the answer int ans = 0 ; for ( int i = 0 ; i < N - 1 ; i++) // If sum is greater or equal to K if (left[i] + right[i + 1 ] >= K) ans++; return ans; } public static void main (String[] args) { int K = 5 ; int []A = { 1 , 2 , 3 , 4 , 5 }; int N = A.length; // Function Call System.out.println(totalCuts(N, K, A)); } } // This code is contributed by Pushpesh raj. |
Python3
# Python3 code to implement the approach # Function to find the number of ways def totalCuts(N, K, A) : # Arrays to store the prefix max and # suffix min for the current position left = [ 0 ] * N; right = [ 0 ] * N; left[ 0 ] = A[ 0 ]; right[N - 1 ] = A[N - 1 ]; # Calculating the prefix maximum for i in range ( 1 , N) : left[i] = max (A[i], left[i - 1 ]); # Calculating the suffix minimum for i in range (N - 2 , - 1 , - 1 ) : right[i] = min (A[i], right[i + 1 ]); # Initialize the answer ans = 0 ; for i in range (N - 1 ) : # If sum is greater or equal to K if (left[i] + right[i + 1 ] > = K) : ans + = 1 ; return ans; # Driver Code if __name__ = = "__main__" : K = 5 ; A = [ 1 , 2 , 3 , 4 , 5 ]; N = len (A); # Function Call print (totalCuts(N, K, A)); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; class GFG { // Function to find the number of ways static int totalCuts( int N, int K, int [] A) { // Arrays to store the prefix max and // suffix min for the current position int [] left = new int [N]; int [] right = new int [N]; left[0] = A[0]; right[N - 1] = A[N - 1]; // Calculating the prefix maximum for ( int i = 1; i < N; i++) left[i] = Math.Max(A[i], left[i - 1]); // Calculating the suffix minimum for ( int i = N - 2; i >= 0; i--) right[i] = Math.Min(A[i], right[i + 1]); // Initialize the answer int ans = 0; for ( int i = 0; i < N - 1; i++) // If sum is greater or equal to K if (left[i] + right[i + 1] >= K) ans++; return ans; } public static void Main() { int K = 5; int [] A = { 1, 2, 3, 4, 5 }; int N = A.Length; // Function Call Console.WriteLine(totalCuts(N, K, A)); } } // This code is contributed by Samim Hossain Mondal |
Javascript
// javascript code to implement the approach // Function to find the number of ways function totalCuts(N, K, A) { // Arrays to store the prefix max and // suffix min for the current position let left= Array(N); let right= Array(N); left[0] = A[0]; right[N - 1] = A[N - 1]; // Calculating the prefix maximum for (let i = 1; i < N; i++) left[i] = Math.max(A[i], left[i - 1]); // Calculating the suffix minimum for (let i = N - 2; i >= 0; i--) right[i] = Math.min(A[i], right[i + 1]); // Initialize the answer let ans = 0; for (let i = 0; i < N - 1; i++) // If sum is greater or equal to K if (left[i] + right[i + 1] >= K) ans++; return ans; } // Driver Code let K = 5; let A = [ 1, 2, 3, 4, 5 ]; let N = A.length; // Function Call console.log(totalCuts(N, K, A)); // This code is contributed by ksam24000 |
3
Time Complexity: O(N)
Auxiliary Space: O(N)