Recuento de subarreglos con suma de al menos K

Dada una array arr[] de tamaño N y un entero K > 0 . La tarea es encontrar el número de subarreglos con una suma de al menos K .
Ejemplos: 
 

Entrada: arr[] = {6, 1, 2, 7}, K = 10 
Salida:
{6, 1, 2, 7} y {1, 2, 7} son los únicos subarreglos válidos.
Entrada: arr[] = {3, 3, 3}, K = 5 
Salida:
 

Enfoque: para un índice izquierdo fijo (digamos l ), ​​intente encontrar el primer índice a la derecha de l (digamos r ) tal que (arr[l] + arr[l + 1] + … + arr[r]) ≥ k _ Luego agregue N – r + 1 a la respuesta requerida. Repita este proceso para todos los índices de la izquierda.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to return the number of
// subarrays with sum atleast k
int k_sum(int a[], int n, int k)
{
    // To store the right index
    // and the current sum
    int r = 0, sum = 0;
  
    // To store the number of sub-arrays
    int ans = 0;
  
    // For all left indexes
    for (int l = 0; l < n; l++) {
  
        // Get elements till current sum
        // is less than k
        while (sum < k) {
            if (r == n)
                break;
            else {
                sum += a[r];
                r++;
            }
        }
  
        // No such subarray is possible
        if (sum < k)
            break;
  
        // Add all possible subarrays
        ans += n - r + 1;
  
        // Remove the left most element
        sum -= a[l];
    }
  
    // Return the required answer
    return ans;
}
  
// Driver code
int main()
{
    int a[] = { 6, 1, 2, 7 }, k = 10;
    int n = sizeof(a) / sizeof(a[0]);
  
    cout << k_sum(a, n, k);
  
    return 0;
}

Java

// Java implementation of the approach 
class GFG
{
      
    // Function to return the number of 
    // subarrays with sum atleast k 
    static int k_sum(int a[], int n, int k) 
    { 
        // To store the right index 
        // and the current sum 
        int r = 0, sum = 0; 
      
        // To store the number of sub-arrays 
        int ans = 0; 
      
        // For all left indexes 
        for (int l = 0; l < n; l++)
        { 
      
            // Get elements till current sum 
            // is less than k 
            while (sum < k) 
            { 
                if (r == n) 
                    break; 
                else 
                { 
                    sum += a[r]; 
                    r++; 
                } 
            } 
      
            // No such subarray is possible 
            if (sum < k) 
                break; 
      
            // Add all possible subarrays 
            ans += n - r + 1; 
      
            // Remove the left most element 
            sum -= a[l]; 
        } 
      
        // Return the required answer 
        return ans; 
    } 
      
    // Driver code 
    public static void main (String[] args)
    { 
        int a[] = { 6, 1, 2, 7 }, k = 10; 
        int n = a.length; 
      
        System.out.println(k_sum(a, n, k)); 
    }
}
  
// This code is contributed by kanugargng

Python3

# Python3 implementation of the approach
  
# Function to return the number of
# subarrays with sum atleast k
def k_sum(a, n, k):
      
    # To store the right index
    # and the current sum
    r, sum = 0, 0;
  
    # To store the number of sub-arrays
    ans = 0;
  
    # For all left indexes
    for l in range(n):
  
        # Get elements till current sum
        # is less than k
        while (sum < k):
            if (r == n):
                break;
            else:
                sum += a[r];
                r += 1;
  
        # No such subarray is possible
        if (sum < k):
            break;
  
        # Add all possible subarrays
        ans += n - r + 1;
  
        # Remove the left most element
        sum -= a[l]; 
    # Return the required answer
    return ans;
  
# Driver code
a = [ 6, 1, 2, 7 ]; k = 10;
n = len(a);
  
print(k_sum(a, n, k));
  
# This code contributed by PrinciRaj1992

C#

// C# implementation of the approach 
using System;
  
class GFG
{
      
    // Function to return the number of 
    // subarrays with sum atleast k 
    static int k_sum(int []a, int n, int k) 
    { 
        // To store the right index 
        // and the current sum 
        int r = 0, sum = 0; 
      
        // To store the number of sub-arrays 
        int ans = 0; 
      
        // For all left indexes 
        for (int l = 0; l < n; l++)
        { 
      
            // Get elements till current sum 
            // is less than k 
            while (sum < k) 
            { 
                if (r == n) 
                    break; 
                else
                { 
                    sum += a[r]; 
                    r++; 
                } 
            } 
      
            // No such subarray is possible 
            if (sum < k) 
                break; 
      
            // Add all possible subarrays 
            ans += n - r + 1; 
      
            // Remove the left most element 
            sum -= a[l]; 
        } 
      
        // Return the required answer 
        return ans; 
    } 
      
    // Driver code 
    public static void Main()
    { 
        int []a = { 6, 1, 2, 7 };
        int k = 10; 
        int n = a.Length; 
      
        Console.WriteLine(k_sum(a, n, k)); 
    }
}
  
// This code is contributed by AnkitRai01

Javascript

<script>
// Javascript implementation of the approach
  
// Function to return the number of
// subarrays with sum atleast k
function k_sum(a, n, k)
{
  
    // To store the right index
    // and the current sum
    let r = 0, sum = 0;
  
    // To store the number of sub-arrays
    let ans = 0;
  
    // For all left indexes
    for (let l = 0; l < n; l++) {
  
        // Get elements till current sum
        // is less than k
        while (sum < k) {
            if (r == n)
                break;
            else {
                sum += a[r];
                r++;
            }
        }
  
        // No such subarray is possible
        if (sum < k)
            break;
  
        // Add all possible subarrays
        ans += n - r + 1;
  
        // Remove the left most element
        sum -= a[l];
    }
  
    // Return the required answer
    return ans;
}
  
// Driver code
let a = [6, 1, 2, 7], k = 10;
let n = a.length;
  
document.write(k_sum(a, n, k));
  
// This code is contributed by _saurabh_jaiswal.
</script>
Producción: 

2

 

Complejidad temporal: O(r * k)

Espacio Auxiliar: O(1)

Tema relacionado: Subarrays, subsecuencias y subconjuntos en array

Publicación traducida automáticamente

Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *