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
Longest subarray having sum of elements atmost K by generating all subarray.
Generate all the subarrays, and keep updating the largest subarray whose sum is less than or equal to K.
Below is the implementation of the above idea:
// A C++ program to find longest subarray with
// sum of elements at-least k.
#include <bits/stdc++.h>
using namespace std;
// function to find the length of largest subarray
// having sum atmost k.
int atMostSum(int arr[], int n, int k)
{
int result = INT_MIN;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
sum += arr[j];
if (sum <= k) {
result = max(result, (j - i + 1));
}
else {
break;
}
}
}
return result;
}
// Driver function
int main()
{
int arr[] = { 1, 2, 1, 0, 1, 1, 0 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
int result = atMostSum(arr, n, k);
if (result == INT_MIN) {
cout << "No such subarray found";
}
else {
cout << "The length of largest subarray having sum "
"atmost k: "
<< result << endl;
}
return 0;
}
import java.util.Arrays;
class Main
{
// function to find the length of largest subarray
// having sum atmost k.
public static int atMostSum(int[] arr, int n, int k)
{
int result = Integer.MIN_VALUE;
// Iterate over the array
for (int i = 0; i < n; i++) {
int sum = 0;
// Find sum of every subarray
for (int j = i; j < n; j++) {
sum += arr[j];
// Check if sum of subarray is at least k
if (sum <= k) {
// Maximise the result
result = Math.max(result, (j - i + 1));
}
else {
break;
}
}
}
// Return the result
return result;
}
public static void main(String[] args)
{
int[] arr = { 1, 2, 1, 0, 1, 1, 0 };
int n = arr.length;
int k = 4;
int result = atMostSum(arr, n, k);
if (result == Integer.MIN_VALUE) {
System.out.println("No such subarray found");
}
else {
System.out.println(
"The length of largest subarray having sum "
+ "atmost k: " + result);
}
}
}
// This code is contributed by divya_p123.
using System;
class Gfg {
// Function to find the length of largest subarray
// having sum at most k
public static int AtMostSum(int[] arr, int n, int k)
{
int result = int.MinValue;
// Iterate over the array
for (int i = 0; i < n; i++) {
int sum = 0;
// Find sum of every subarray
for (int j = i; j < n; j++) {
sum += arr[j];
// Check if sum of subarray is at most k
if (sum <= k) {
// Maximize the result
result = Math.Max(result, (j - i + 1));
}
else {
break;
}
}
}
// Return the result
return result;
}
public static void Main(string[] args)
{
int[] arr = { 1, 2, 1, 0, 1, 1, 0 };
int n = arr.Length;
int k = 4;
int result = AtMostSum(arr, n, k);
if (result == int.MinValue) {
Console.WriteLine("No such subarray found");
}
else {
Console.WriteLine(
"The length of largest subarray having sum at most k: "
+ result);
}
}
}
// JavaScript program to find the length of the largest subarray
// having sum at most k
function atMostSum(arr, n, k) {
let result = -Infinity; // initialize result with negative infinity
// Iterate over the array
for (let i = 0; i < n; i++)
{
let sum = 0; // initialize the sum for each subarray
// Find sum of every subarray
for (let j = i; j < n; j++)
{
sum += arr[j]; // add the current element to the sum
// Check if sum of subarray is at most k
if (sum <= k)
{
// Maximize the result
result = Math.max(result, (j - i + 1));
} else {
break; // if sum becomes greater than k, break the loop
}
}
}
// Return the result
return result;
}
// Driver code
let arr = [1, 2, 1, 0, 1, 1, 0];
let n = arr.length;
let k = 4;
let result = atMostSum(arr, n, k);
if (result == -Infinity) {
console.log("No such subarray found");
} else {
console.log("The length of largest subarray having sum at most k:", result);
}
// This code is contributed by Prajwal Kandekar
# Python program to find the length of the largest subarray
# having sum at most k
def atMostSum(arr, n, k):
result = float('-inf') # initialize result with negative infinity
# Iterate over the array
for i in range(n):
sum = 0 # initialize the sum for each subarray
# Find sum of every subarray
for j in range(i, n):
sum += arr[j] # add the current element to the sum
# Check if sum of subarray is at most k
if sum <= k:
# Maximize the result
result = max(result, (j - i + 1))
else:
break # if sum becomes greater than k, break the loop
# Return the result
return result
# Driver code
arr = [1, 2, 1, 0, 1, 1, 0]
n = len(arr)
k = 4
result = atMostSum(arr, n, k)
if result == float('-inf'):
print("No such subarray found")
else:
print("The length of largest subarray having sum at most k:", result)
Output
The length of largest subarray having sum atmost k: 5
Time Complexity : O(n^2)
Auxiliary space: O(1)
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.net or mail your article to review-team@w3wiki.net. See your article appearing on the w3wiki main page and help other Beginner.
Contact Us