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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
