Dada una array de números no negativos y un número no negativo k, encuentre la cantidad de subarreglos que tienen una suma menor que k. Podemos suponer que no hay desbordamiento.
Ejemplos:
Input : arr[] = {2, 5, 6}
K = 10
Output : 4
The subarrays are {2}, {5}, {6} and
{2, 5},
Input : arr[] = {1, 11, 2, 3, 15}
K = 10
Output : 4
{1}, {2}, {3} and {2, 3}
Una solución simple es generar todos los subarreglos de la array y luego contar la cantidad de arrays que tienen una suma menor que K.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to count
// subarrays having sum
// less than k.
#include <bits/stdc++.h>
using namespace std;
// Function to find number
// of subarrays having sum
// less than k.
int countSubarray(int arr[],
int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
// If sum is less than k
// then update sum and
// increment count
if (sum + arr[j] < k) {
sum = arr[j] + sum;
count++;
}
else {
break;
}
}
}
return count;
}
// Driver Code
int main()
{
int array[] = { 1, 11, 2, 3, 15 };
int k = 10;
int size = sizeof(array) / sizeof(array[0]);
int count = countSubarray(array, size, k);
cout << count << "\n";
}
Java
// Java program to count subarrays
// having sum less than k.
import java.io.*;
class GFG {
// Function to find number of
// subarrays having sum less than k.
static int countSubarray(int arr[],
int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
// If sum is less than
// k then update sum and
// increment count
if (sum + arr[j] < k) {
sum = arr[j] + sum;
count++;
}
else {
break;
}
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int array[] = { 1, 11, 2, 3, 15 };
int k = 10;
int size = array.length;
int count = countSubarray(array, size, k);
System.out.println(count);
}
}
// This code is contributed by Sam007
Python3
# python program to count subarrays # having sum less than k. # Function to find number of subarrays # having sum less than k. def countSubarray(arr, n, k): count = 0 for i in range(0, n): sum = 0; for j in range(i, n): # If sum is less than k # then update sum and # increment count if (sum + arr[j] < k): sum = arr[j] + sum count+= 1 else: break return count; # Driver Code array = [1, 11, 2, 3, 15] k = 10 size = len(array) count = countSubarray(array, size, k); print(count) # This code is contributed by Sam007
C#
// C# program to count subarrays
// having sum less than k.
using System;
class GFG {
// Function to find number
// of subarrays having sum
// less than k.
static int countSubarray(int[] arr,
int n, int k)
{
int count = 0;
for (int i = 0; i < n; i++) {
int sum = 0;
for (int j = i; j < n; j++) {
// If sum is less than k
// then update sum and
// increment count
if (sum + arr[j] < k) {
sum = arr[j] + sum;
count++;
}
else {
break;
}
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
int[] array = { 1, 11, 2, 3, 15 };
int k = 10;
int size = array.Length;
int count = countSubarray(array, size, k);
Console.WriteLine(count);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count
// subarrays having sum
// less than k.
// Function to find number
// of subarrays having sum
// less than k.
function countSubarray($arr, $n, $k)
{
$count = 0;
for ($i = 0; $i < $n; $i++)
{
$sum = 0;
for ($j = $i; $j < $n; $j++)
{
// If sum is less than
// k then update sum and
// increment count
if ($sum + $arr[$j] < $k)
{
$sum = $arr[$j] + $sum;
$count++;
}
else
{
break;
}
}
}
return $count;
}
// Driver Code
$array = array(1, 11, 2, 3, 15);
$k = 10;
$size = sizeof($array);
$count = countSubarray($array, $size, $k);
echo $count, "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// javascript program to count subarrays
// having sum less than k.
// Function to find number of
// subarrays having sum less than k.
function countSubarray(arr , n , k)
{
var count = 0;
for (i = 0; i < n; i++)
{
var sum = 0;
for (j = i; j < n; j++)
{
// If sum is less than
// k then update sum and
// increment count
if (sum + arr[j] < k)
{
sum = arr[j] + sum;
count++;
}
else
{
break;
}
}
}
return count;
}
// Driver Code
var array = [ 1, 11, 2, 3, 15 ];
var k = 10;
var size = array.length;
var count = countSubarray(array, size, k);
document.write(count);
// This code is contributed by Rajput-Ji
</script>
Producción :
4
Complejidad del tiempo: O(n^2).
Una solución eficiente se basa en una técnica de ventana deslizante que se puede utilizar para resolver el problema. Usamos dos punteros start y end para representar los puntos de inicio y finalización de la ventana deslizante. (No es que necesitemos encontrar partes contiguas).
Inicialmente, tanto el inicio como el final apuntan al comienzo de la array, es decir, el índice 0. Ahora, intentemos agregar un nuevo elemento el. Hay dos condiciones posibles.
1er caso:
si la suma es menor que k, incrementa el final en una posición. Entonces, las arrays contiguas que produce este paso son (final – inicio). También sumamos el a la suma anterior. Hay tantas arrays como la longitud de la ventana.
2do caso :
Si la suma se vuelve mayor o igual a k, esto significa que debemos restar el elemento inicial de la suma para que la suma nuevamente sea menor que k. Así que ajustamos el borde izquierdo de la ventana incrementando start.
Seguimos el mismo procedimiento hasta end < tamaño del arreglo.
Implementación:
C++
// CPP program to count
// subarrays having sum
// less than k.
#include <bits/stdc++.h>
using namespace std;
// Function to find number
// of subarrays having sum
// less than k.
int countSubarrays(int arr[],
int n, int k)
{
int start = 0, end = 0,
count = 0, sum = arr[0];
while (start < n && end < n) {
// If sum is less than k,
// move end by one position.
// Update count and sum
// accordingly.
if (sum < k) {
end++;
if (end >= start)
count += end - start;
// For last element,
// end may become n
if (end < n)
sum += arr[end];
}
// If sum is greater than or
// equal to k, subtract
// arr[start] from sum and
// decrease sliding window by
// moving start by one position
else {
sum -= arr[start];
start++;
}
}
return count;
}
// Driver Code
int main()
{
int array[] = { 1, 11, 2, 3, 15 };
int k = 10;
int size = sizeof(array) / sizeof(array[0]);
cout << countSubarrays(array, size, k);
}
Java
// Java program to count
// subarrays having sum
// less than k.
import java.io.*;
class GFG {
// Function to find number
// of subarrays having sum
// less than k.
static int countSubarray(int arr[],
int n, int k)
{
int start = 0, end = 0;
int count = 0, sum = arr[0];
while (start < n && end < n) {
// If sum is less than k,
// move end by one position.
// Update count and sum
// accordingly.
if (sum < k) {
end++;
if (end >= start)
count += end - start;
// For last element,
// end may become n.
if (end < n)
sum += arr[end];
}
// If sum is greater than or
// equal to k, subtract
// arr[start] from sum and
// decrease sliding window by
// moving start by one position
else {
sum -= arr[start];
start++;
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int array[] = { 1, 11, 2, 3, 15 };
int k = 10;
int size = array.length;
int count = countSubarray(array, size, k);
System.out.println(count);
}
}
// This code is contributed by Sam007
Python 3
# Python 3 program to count subarrays # having sum less than k. # Function to find number of subarrays # having sum less than k. def countSubarrays(arr, n, k): start = 0 end = 0 count = 0 sum = arr[0] while (start < n and end < n) : # If sum is less than k, move end # by one position. Update count and # sum accordingly. if (sum < k) : end += 1 if (end >= start): count += end - start # For last element, end may become n if (end < n): sum += arr[end] # If sum is greater than or equal to k, # subtract arr[start] from sum and # decrease sliding window by moving # start by one position else : sum -= arr[start] start += 1 return count # Driver Code if __name__ == "__main__": array = [ 1, 11, 2, 3, 15 ] k = 10 size = len(array) print(countSubarrays(array, size, k)) # This code is contributed by ita_c
C#
// C# program to count
// subarrays having sum
// less than k.
using System;
class GFG {
// Function to find number
// of subarrays having sum
// less than k.
static int countSubarray(int[] arr,
int n, int k)
{
int start = 0, end = 0;
int count = 0, sum = arr[0];
while (start < n && end < n) {
// If sum is less than k,
// move end by one position.
// Update count and sum
// accordingly.
if (sum < k) {
end++;
if (end >= start)
count += end - start;
// For last element,
// end may become n.
if (end < n)
sum += arr[end];
}
// If sum is greater than or
// equal to k, subtract
// arr[start] from sum and
// decrease sliding window by
// moving start by one position
else {
sum -= arr[start];
start++;
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
int[] array = { 1, 11, 2, 3, 15 };
int k = 10;
int size = array.Length;
int count = countSubarray(array, size, k);
Console.WriteLine(count);
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP program to count
// subarrays having sum
// less than k.
// Function to find number
// of subarrays having sum
// less than k.
function countSubarrays($arr,
$n, $k)
{
$start = 0;
$end = 0;
$count = 0;
$sum = $arr[0];
while ($start < $n && $end < $n)
{
// If sum is less than k,
// move end by one position.
// Update count and sum
// accordingly.
if ($sum < $k)
{
$end++;
if ($end >= $start)
$count += $end - $start;
// For last element,
// end may become n
if ($end < $n)
$sum += $arr[$end];
}
// If sum is greater than or
// equal to k, subtract
// arr[start] from sum and
// decrease sliding window by
// moving start by one position
else
{
$sum -= $arr[$start];
$start++;
}
}
return $count;
}
// Driver Code
$array =array (1, 11, 2, 3, 15);
$k = 10;
$size = sizeof($array) ;
echo countSubarrays($array, $size, $k);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to count
// subarrays having sum
// less than k.
// Function to find number
// of subarrays having sum
// less than k.
function countSubarray(arr, n, k)
{
let start = 0, end = 0;
let count = 0, sum = arr[0];
while (start < n && end < n) {
// If sum is less than k,
// move end by one position.
// Update count and sum
// accordingly.
if (sum < k) {
end++;
if (end >= start)
count += end - start;
// For last element,
// end may become n.
if (end < n)
sum += arr[end];
}
// If sum is greater than or
// equal to k, subtract
// arr[start] from sum and
// decrease sliding window by
// moving start by one position
else {
sum -= arr[start];
start++;
}
}
return count;
}
let array = [ 1, 11, 2, 3, 15 ];
let k = 10;
let size = array.length;
let count = countSubarray(array, size, k);
document.write(count);
</script>
Producción:
4
Complejidad temporal : O(n).
Publicación traducida automáticamente
Artículo escrito por akshitSingh47 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA