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: 2
{6, 1, 2, 7} y {1, 2, 7} son los únicos subarreglos válidos.
Entrada: arr[] = {3, 3, 3}, K = 5
Salida: 3
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>
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