Longest subarray having sum of elements atmost K using Sliding Window Technique
Below is the implementation of the above approach:
// This is a C++ program that finds the length of the
// longest subarray in an array such that the sum of its
// elements is at most k.
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of the largest subarray
// having a sum at most k.
int atMostSum(int arr[], int n, int k)
{
// Initialize the current sum to 0.
int sum = 0;
// Initialize a counter for the current subarray length
// to 0.
int cnt = 0;
// Initialize the maximum subarray length to 0.
int maxcnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > k) {
// Reset the counter if an element is greater
// than k.
sum=0;
cnt = 0;
continue;
}
if ((sum + arr[i]) <= k) {
// Include the current element in the subarray.
// Increment the subarray length.
cnt++;
sum += arr[i];
}
else {
cnt++;
sum += arr[i];
// If the sum exceeds k, remove elements from
// the subarray until the sum is less than or
// equal to k.
while (sum > k) {
sum -= arr[i - cnt + 1];
cnt--;
}
}
// Update the maximum subarray length.
maxcnt = max(cnt, maxcnt);
}
return maxcnt;
}
int main()
{
int arr[] = { 1, 2, 1, 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
// Print the length of the longest
// subarray with sum at most k.
cout << atMostSum(arr, n, k);
return 0;
}
public class LongestSubarraySumAtMostK {
// Function to find the length of the largest subarray
// having a sum at most k.
public static int atMostSum(int[] arr, int n, int k) {
// Initialize the current sum to 0.
int sum = 0;
// Initialize a counter for the current subarray length
// to 0.
int cnt = 0;
// Initialize the maximum subarray length to 0.
int maxcnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] > k) {
// Reset the counter if an element is greater
// than k.
cnt = 0;
continue;
}
if ((sum + arr[i]) <= k) {
// Include the current element in the subarray.
// Increment the subarray length.
cnt++;
sum += arr[i];
} else {
cnt++;
sum += arr[i];
// If the sum exceeds k, remove elements from
// the subarray until the sum is less than or
// equal to k.
while (sum > k) {
sum -= arr[i - cnt + 1];
cnt--;
}
}
// Update the maximum subarray length.
maxcnt = Math.max(cnt, maxcnt);
}
return maxcnt;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 1, 0, 1, 1, 0 };
int n = arr.length;
int k = 4;
// Print the length of the longest
// subarray with sum at most k.
System.out.println(atMostSum(arr, n, k));
}
}
# Function to find the length of the largest subarray
# having a sum at most k.
def atMostSum(arr, k):
# Initialize the current sum to 0.
sum_val = 0
# Initialize a counter for the current subarray length
# to 0.
cnt = 0
# Initialize the maximum subarray length to 0.
maxcnt = 0
for i in range(len(arr)):
if arr[i] > k:
# Reset the counter if an element is greater
# than k.
cnt = 0
continue
if (sum_val + arr[i]) <= k:
# Include the current element in the subarray.
# Increment the subarray length.
cnt += 1
sum_val += arr[i]
else:
cnt += 1
sum_val += arr[i]
# If the sum exceeds k, remove elements from
# the subarray until the sum is less than or
# equal to k.
while sum_val > k:
sum_val -= arr[i - cnt + 1]
cnt -= 1
# Update the maximum subarray length.
maxcnt = max(cnt, maxcnt)
return maxcnt
# Main function
if __name__ == "__main__":
arr = [1, 2, 1, 0, 1, 1, 0]
k = 4
# Print the length of the longest
# subarray with sum at most k.
print(atMostSum(arr, k))
using System;
class Program
{
// Function to find the length of the largest subarray
// having a sum at most k.
static int AtMostSum(int[] arr, int n, int k)
{
// Initialize the current sum to 0.
int sum = 0;
// Initialize a counter for the current subarray length
// to 0.
int cnt = 0;
// Initialize the maximum subarray length to 0.
int maxcnt = 0;
for (int i = 0; i < n; i++)
{
if (arr[i] > k)
{
// Reset the counter if an element is greater
// than k.
cnt = 0;
continue;
}
if ((sum + arr[i]) <= k)
{
// Include the current element in the subarray.
// Increment the subarray length.
cnt++;
sum += arr[i];
}
else
{
cnt++;
sum += arr[i];
// If the sum exceeds k, remove elements from
// the subarray until the sum is less than or
// equal to k.
while (sum > k)
{
sum -= arr[i - cnt + 1];
cnt--;
}
}
// Update the maximum subarray length.
maxcnt = Math.Max(cnt, maxcnt);
}
return maxcnt;
}
static void Main(string[] args)
{
int[] arr = { 1, 2, 1, 0, 1, 1, 0 };
int n = arr.Length;
int k = 4;
// Print the length of the longest subarray with sum at most k.
Console.WriteLine(AtMostSum(arr, n, k));
}
}
// Function to find the length of the largest subarray
// having a sum at most k.
function atMostSum(arr, k) {
// Initialize the current sum to 0.
let sum = 0;
// Initialize a counter for the current subarray length to 0.
let cnt = 0;
// Initialize the maximum subarray length to 0.
let maxcnt = 0;
for (let i = 0; i < arr.length; i++) {
if (arr[i] > k) {
// Reset the counter if an element is greater than k.
cnt = 0;
continue;
}
if (sum + arr[i] <= k) {
// Include the current element in the subarray.
// Increment the subarray length.
cnt++;
sum += arr[i];
} else {
cnt++;
sum += arr[i];
// If the sum exceeds k, remove elements from the subarray
// until the sum is less than or equal to k.
while (sum > k) {
sum -= arr[i - cnt + 1];
cnt--;
}
}
// Update the maximum subarray length.
maxcnt = Math.max(cnt, maxcnt);
}
return maxcnt;
}
// Main function
function main() {
const arr = [1, 2, 1, 0, 1, 1, 0];
const k = 4;
// Print the length of the longest subarray with sum at most k.
console.log(atMostSum(arr, k));
}
main();
Output
5
Time Complexity : O(n), where n represents the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
This article is contributed by Kshitiz gupta. If you like w3wiki and would like to contribute, you can also write an article using write.w3wiki.org or mail your article to review-team@w3wiki.org. See your article appearing on the w3wiki main page and help other Geeks.
Longest subarray having sum of elements atmost K
Given an array arr[] of size N and an integer K, the task is to find the length of the largest subarray having the sum of its elements at most K, where K > 0.
Examples:
Input: arr[] = {1, 2, 1, 0, 1, 1, 0}, k = 4
Output: 5
Explanation: {1, 2, 1} => sum = 4, length = 3 {1, 2, 1, 0}, {2, 1, 0, 1} => sum = 4, length = 4 {1, 0, 1, 1, 0} =>5 sum = 3, length = 5Input: 8, 2, 4, 0, 1, 1, 0, K = 9
Output: 6
Contact Us