Written in C++, find the number of subarrays whose sum is less than K

In this post, we will find the number of subarrays with sum less than K using C. In this problem, we have an array arr[] and an integer K. Now we need to find the subarrays whose sum is less than K. Below is the example −

Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}

Methods to find the solution

Now we will use two different methods to solve the given problem-

Brute force cracking

In this method we will iterate through all sub-arrays and calculate their sum and if the sum is less than k then compare with k to increase our answer.

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    for(int i = 0; i < size; i++){ // outer loop.
        int sum = 0;
        for(int j = i; j < size; j++){ // inner loop.
            sum = sum + arr[j];
            if(sum < k) // comparing with k.
               ans++; // incrementing our ans if sum is less than k.
        }
    }
    cout << ans << "\n";
    return 0;
}

Output

4

However, this method is not very good because its time complexity is very highO(N*N), where n is the size of the array.

We'll look for alternative solutions using the sliding window approach (which will help us reduce the time complexity of the program).

Efficient method

Different from brute force attack

Efficient method

strong>, we will not traverse all sub-arrays. Instead, only when the sum of the subarrays exceeds k , we iterate and move the left boundary to the right boundary and repeat until the entire array is traversed.

Example

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 11, 2, 3, 15}; // given array
    int k = 10; // given k
    int size = sizeof(arr) / sizeof(int); // size of our array.
    int ans = 0; // counter variable.
    int start = 0; // left border.
    int end = 0; // right border.
    int sum = 0;
    while(end < size && start < size){ // till the whole array is traversed.
        while(sum >= k && start < end){
           sum = sum - arr[start];
           start++;
        }
        if(end >= start)
           ans = ans + end - start;
        sum += arr[end];
        end++;
    }
    cout << ans << "\n";
    return 0;
}

Output

4

We use Sliding Window Technique to make our program faster or better when dealing with larger constraints Efficient.

Explanation of the above code

In this approach we usually iterate until our sum is less than k and increment our answer based on it, this is the key change in the code that happens when the sum When it is greater than or equal to k. In this case, we start incrementing our left bound until it is less than or equal to k or the sum is greater than or equal to k. As our processing proceeds further, it iterates through other possible subarrays that may be formed. The sum of these new subarrays less than k is added to our answer, so our answer is incremented.

Compared with the previous brute force solution, this method is very efficient because its time complexity is O(N), where N is the number of our array size.

Conclusion

In this article, we used sliding window technique to solve the problem of finding the number of subarrays whose sum is less than k. We also learned the C program for this problem and our complete approach to solving it (both trivial and efficient). We can write the same program in other languages ​​like C, Java, Python and others. Hope you find this article helpful.

The above is the detailed content of Written in C++, find the number of subarrays whose sum is less than K. For more information, please follow other related articles on the PHP Chinese website!