Remove minimum elements from ends of array so that sum decreases by at least K | O(N)
Given an array arr[] consisting of N elements, the task is to remove minimum number of elements from the ends of the array such that the total sum of the array decreases by at least K. Note that K will always be less than or equal to the sum of all the elements of the array.
Examples:
Input: arr[] = {1, 11, 5, 5}, K = 11
Output: 2
After removing two elements form the left
end, the sum decreases by 1 + 11 = 12.
Thus, the answer is 2.Input: arr[] = {1, 2, 3}, K = 6
Output: 3
Approach: A dynamic programming-based approach has already been discussed in another post. In this article, an approach using the two-pointer technique will be discussed. It can be observed that the task is to find the longest sub-array with the sum of its elements at most sum(arr) – K where sum(arr) is the sum of all the elements of the array arr[].
Let the length of such subarray be L. Thus, the minimum number of elements to be removed from the array will be equal to N – L. To find the length of longest such subarray, refer this article.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count of minimum// elements to be removed from the ends// of the array such that the sum of the// array decrease by at least Kint minCount(int* arr, int n, int k){ // To store the final answer int ans = 0; // Maximum possible sum required int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; sum -= k; // Left point int l = 0; // Right pointer int r = 0; // Total current sum int tot = 0; // Two pointer loop while (l < n) { // If the sum fits if (tot <= sum) { // Update the answer ans = max(ans, r - l); if (r == n) break; // Update the total sum tot += arr[r++]; } else { // Increment the left pointer tot -= arr[l++]; } } return (n - ans);}// Driver codeint main(){ int arr[] = { 1, 11, 5, 5 }; int n = sizeof(arr) / sizeof(int); int k = 11; cout << minCount(arr, n, k); return 0;} |
Java
// Java implementation of the approach class GFG{ // Function to return the count of minimum // elements to be removed from the ends // of the array such that the sum of the // array decrease by at least K static int minCount(int arr[], int n, int k) { // To store the final answer int ans = 0; // Maximum possible sum required int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; sum -= k; // Left point int l = 0; // Right pointer int r = 0; // Total current sum int tot = 0; // Two pointer loop while (l < n) { // If the sum fits if (tot <= sum) { // Update the answer ans = Math.max(ans, r - l); if (r == n) break; // Update the total sum tot += arr[r++]; } else { // Increment the left pointer tot -= arr[l++]; } } return (n - ans); } // Driver code public static void main (String[] args) { int arr[] = { 1, 11, 5, 5 }; int n = arr.length; int k = 11; System.out.println(minCount(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to return the count of minimum # elements to be removed from the ends # of the array such that the sum of the # array decrease by at least K def minCount(arr, n, k) : # To store the final answer ans = 0; # Maximum possible sum required sum = 0; for i in range(n) : sum += arr[i]; sum -= k; # Left point l = 0; # Right pointer r = 0; # Total current sum tot = 0; # Two pointer loop while (l < n) : # If the sum fits if (tot <= sum) : # Update the answer ans = max(ans, r - l); if (r == n) : break; # Update the total sum tot += arr[r]; r += 1 else : # Increment the left pointer tot -= arr[l]; l += 1 return (n - ans); # Driver code if __name__ == "__main__" : arr = [ 1, 11, 5, 5 ]; n = len(arr); k = 11; print(minCount(arr, n, k)); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the approach using System;class GFG{ // Function to return the count of minimum // elements to be removed from the ends // of the array such that the sum of the // array decrease by at least K static int minCount(int []arr, int n, int k) { // To store the final answer int ans = 0; // Maximum possible sum required int sum = 0; for (int i = 0; i < n; i++) sum += arr[i]; sum -= k; // Left point int l = 0; // Right pointer int r = 0; // Total current sum int tot = 0; // Two pointer loop while (l < n) { // If the sum fits if (tot <= sum) { // Update the answer ans = Math.Max(ans, r - l); if (r == n) break; // Update the total sum tot += arr[r++]; } else { // Increment the left pointer tot -= arr[l++]; } } return (n - ans); } // Driver code public static void Main() { int []arr = { 1, 11, 5, 5 }; int n = arr.Length; int k = 11; Console.WriteLine(minCount(arr, n, k)); } }// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the approach// Function to return the count of minimum// elements to be removed from the ends// of the array such that the sum of the// array decrease by at least Kfunction minCount(arr, n, k){ // To store the final answer var ans = 0; // Maximum possible sum required var sum = 0; for (var i = 0; i < n; i++) sum += arr[i]; sum -= k; // Left point var l = 0; // Right pointer var r = 0; // Total current sum var tot = 0; // Two pointer loop while (l < n) { // If the sum fits if (tot <= sum) { // Update the answer ans = Math.max(ans, r - l); if (r == n) break; // Update the total sum tot += arr[r++]; } else { // Increment the left pointer tot -= arr[l++]; } } return (n - ans);}// Driver codevar arr = [1, 11, 5, 5 ];var n = arr.length;var k = 11;document.write( minCount(arr, n, k));// This code is contributed by noob2000.</script> |
Output:
2
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
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 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
