Total cuts such that sum of largest of left and smallest of right is atleast K
Given an array A[] of size N and an integer K, the task is to find the total number of cuts that you can make such that for each cut these two conditions are satisfied:
- A cut divides an array into two parts of equal or unequal length (non-zero).
- 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: N = 3, K = 3, A[] = {1, 2, 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 = 5(satisfies the condition)
Input: N = 5, K = 5, A[] = {1, 2, 3, 4, 5}
Output: 3
Explanation:
- {1, 2} and {3, 4, 5} -> 2+3 = 5
- {1, 2, 3} and {4, 5} -> 3+4 = 7
- {1, 2, 3, 4} and {5} -> 4+5 = 9
Approach: The problem can be solved based on the following idea:
Create an array and for each index store the minimum till that from right. Now iterate from the left and keep finding the max till now. If that max and min from end till the next index give a sum of at least K, then we can have a cut there.
Follow the steps mentioned below to implement the idea:
- Create an array (say minRight[]) to store the minimum till an index from the right.
- Iterate from i = N-1 to 0 and compare the current element with minRight[i+1] to fill the array.
- After the minRight[] array is filled, start iterating from i = 0 to N:
- If the sum of max till i and minRight[i+1] is at least K, increment the answer.
- Return the answer.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Function to find the total // number of possible cuts int totalCuts( int N, int K, int A[]) { int max = -1; int index = 0, count = 0; int minRight[N]; minRight[N - 1] = A[N - 1]; // Loop to store the minimum from // right end till i for ( int i = N - 2; i >= 0; i--) { if (A[i] < minRight[i + 1]) minRight[i] = A[i]; else minRight[i] = minRight[i + 1]; } // Loop to find the number of // possible cuts for ( int i = 0; i < N - 1; i++) { max = max > A[i] ? max : A[i]; if (max + minRight[i + 1] >= K) count++; } return count; } // Driver code int main() { int N = 3; int K = 3; int A[] = { 1, 2, 3 }; // Function call int result = totalCuts(N, K, A); cout << result << endl; return 0; } |
Java
// Java code to implement the approach import java.util.*; public class Main { // Function to find the total // number of possible cuts public static int totalCuts( int N, int K, int [] A) { int max = - 1 ; int index = 0 , count = 0 ; int minRight[] = new int [N]; minRight[N - 1 ] = A[N - 1 ]; // Loop to store the minimum from // right end till i for ( int i = N - 2 ; i >= 0 ; i--) { if (A[i] < minRight[i + 1 ]) minRight[i] = A[i]; else minRight[i] = minRight[i + 1 ]; } // Loop to find the number of // possible cuts for ( int i = 0 ; i < N - 1 ; i++) { max = Math.max(max, A[i]); if (max + minRight[i + 1 ] >= K) count++; } return count; } // Driver code public static void main(String[] args) { int N = 3 ; int K = 3 ; int [] A = { 1 , 2 , 3 }; // Function call int result = totalCuts(N, K, A); System.out.println(result); } } |
Python3
# Function to find the total # number of possible cuts def totalCuts(N, K, A): max_val = - 1 index = 0 count = 0 minRight = [ 0 ] * N minRight[N - 1 ] = A[N - 1 ] # Loop to store the minimum from # right end till i for i in range (N - 2 , - 1 , - 1 ): if A[i] < minRight[i + 1 ]: minRight[i] = A[i] else : minRight[i] = minRight[i + 1 ] # Loop to find the number of # possible cuts for i in range (N - 1 ): max_val = max (max_val, A[i]) if max_val + minRight[i + 1 ] > = K: count + = 1 return count # Driver code N = 3 K = 3 A = [ 1 , 2 , 3 ] # Function call result = totalCuts(N, K, A) print (result) |
C#
using System; public class GFG{ // Function to find the total // number of possible cuts public static int TotalCuts( int N, int K, int [] A) { int max = -1; int index = 0, count = 0; int [] minRight = new int [N]; minRight[N - 1] = A[N - 1]; // Loop to store the minimum from // right end till i for ( int i = N - 2; i >= 0; i--) { if (A[i] < minRight[i + 1]) minRight[i] = A[i]; else minRight[i] = minRight[i + 1]; } // Loop to find the number of // possible cuts for ( int i = 0; i < N - 1; i++) { max = max > A[i] ? max : A[i]; if (max + minRight[i + 1] >= K) count++; } return count; } // Driver code public static void Main() { int N = 3; int K = 3; int [] A = { 1, 2, 3 }; // Function call int result = TotalCuts(N, K, A); Console.WriteLine(result); } } |
Javascript
// Javascript code to implement the approach // Function to find the total // number of possible cuts function totalCuts(N, K, A) { let max = -1; let index = 0, count = 0; const minRight = new Array(N); minRight[N - 1] = A[N - 1]; // Loop to store the minimum from // right end till i for (let i = N - 2; i >= 0; i--) { if (A[i] < minRight[i + 1]) minRight[i] = A[i]; else minRight[i] = minRight[i + 1]; } // Loop to find the number of // possible cuts for (let i = 0; i < N - 1; i++) { max = max > A[i] ? max : A[i]; if (max + minRight[i + 1] >= K) count++; } return count; } // Driver code const N = 3; const K = 3; const A = [1, 2, 3]; // Function call const result = totalCuts(N, K, A); console.log(result); |
2
Time Complexity: O(N)
Auxiliary Space: O(N)