Número de subarreglos que tienen una suma absoluta mayor que K | Conjunto-2

Dada una array de enteros arr[] de longitud N que consta de enteros positivos y negativos, la tarea es encontrar el número de sub-arrays con el valor absoluto de sum mayor que un número positivo K dado . 

Ejemplos:  

Entrada: arr[] = {-1, 0, 1}, K = 0 
Salida: 4 
Todos los subconjuntos posibles y la suma total: 
{-1} = -1 
{0} = 0 
{1} = 1 
{- 1, 0} = -1 
{0, 1} = 1 
{-1, 0, 1} = 0 
Por lo tanto, 4 subarreglos tienen un 
valor absoluto de suma mayor que 0.
Entrada: arr[] = {2, 3, 4}, K = 4 
Salida: 3 
 

Enfoque: aquí se analiza un enfoque similar que funciona en una array de enteros positivos .
En este artículo, veremos un algoritmo que resuelve este problema para enteros positivos y negativos.  

1. Cree una array de suma de prefijos de la array dada.
2. Ordene la array de suma de prefijos.
3. Cree la variable ans , encuentre el número de elementos en la array de suma de prefijos con un valor menor que -K o mayor que K , e inicialice ans con este valor.
4. Ahora, itere la array ordenada de suma de prefijos y para cada índice i , encuentre el índice del primer elemento con un valor mayor que arr[i] + K . Digamos que este índice es j .

Entonces, ans se puede actualizar como ans += N – j, ya que el número de elementos en la array de suma de prefijos mayor que el valor de arr[i]+K será igual a N – j . 
Para encontrar el índice j , realice una búsqueda binaria en la array de suma de prefijos. Específicamente, busque el límite superior del valor de prefix-sum[i] + k . 

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the above approach
#include <bits/stdc++.h>
#define maxLen 30
using namespace std;
 
// Function to find required value
int findCnt(int arr[], int n, int k)
{
    // Variable to store final answer
    int ans = 0;
 
    // Loop to find prefix-sum
    for (int i = 1; i < n; i++) {
        arr[i] += arr[i - 1];
        if (arr[i] > k or arr[i] < -1 * k)
            ans++;
    }
 
    if (arr[0] > k || arr[0] < -1 * k)
        ans++;
 
    // Sorting prefix-sum array
    sort(arr, arr + n);
 
    // Loop to find upper_bound
    // for each element
    for (int i = 0; i < n; i++)
        ans += n -
       (upper_bound(arr, arr + n, arr[i] + k) - arr);
 
    // Returning final answer
    return ans;
}
 
// Driver code
int main()
{
    int arr[] = { -1, 4, -5, 6 };
    int n = sizeof(arr) / sizeof(int);
    int k = 0;
 
    // Function to find required value
    cout << findCnt(arr, n, k);
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
     
static int maxLen = 30;
 
 
// Function to find required value
static int findCnt(int arr[], int n, int k)
{
    // Variable to store final answer
    int ans = 0;
 
    // Loop to find prefix-sum
    for (int i = 1; i < n; i++)
    {
        arr[i] += arr[i - 1];
        if (arr[i] > k || arr[i] < -1 * k)
            ans++;
    }
 
    if (arr[0] > k || arr[0] < -1 * k)
        ans++;
 
    // Sorting prefix-sum array
    Arrays.sort(arr);
 
    // Loop to find upper_bound
    // for each element
    for (int i = 0; i < n; i++)
        ans += n - upper_bound(arr, 0, n, arr[i] + k);
 
    // Returning final answer
    return ans;
}
 
static int upper_bound(int[] a, int low,
                    int high, int element)
{
    while(low < high)
    {
        int middle = low + (high - low)/2;
        if(a[middle] > element)
            high = middle;
        else
            low = middle + 1;
    }
    return low;
}
 
// Driver code
public static void main(String[] args)
{
    int arr[] = { -1, 4, -5, 6 };
    int n = arr.length;
    int k = 0;
 
    // Function to find required value
    System.out.println(findCnt(arr, n, k));
}
}
 
// This code is contributed by 29AjayKumar

// C# implementation of the approach
using System;
 
class GFG
{
    // Function to find required value
    static int findCnt(int []arr, int n, int k)
    {
        // Variable to store final answer
        int ans = 0;
     
        // Loop to find prefix-sum
        for (int i = 1; i < n; i++)
        {
            arr[i] += arr[i - 1];
            if (arr[i] > k || arr[i] < -1 * k)
                ans++;
        }
     
        if (arr[0] > k || arr[0] < -1 * k)
            ans++;
     
        // Sorting prefix-sum array
        Array.Sort(arr);
     
        // Loop to find upper_bound
        // for each element
        for (int i = 0; i < n; i++)
            ans += n - upper_bound(arr, 0, n, arr[i] + k);
     
        // Returning final answer
        return ans;
    }
     
    static int upper_bound(int[] a, int low,
                        int high, int element)
    {
        while(low < high)
        {
            int middle = low + (high - low)/2;
            if(a[middle] > element)
                high = middle;
            else
                low = middle + 1;
        }
        return low;
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = { -1, 4, -5, 6 };
        int n = arr.Length;
        int k = 0;
     
        // Function to find required value
        Console.WriteLine(findCnt(arr, n, k));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the above approach
from bisect import bisect as upper_bound
 
maxLen=30
 
# Function to find required value
def findCnt(arr, n, k):
 
    # Variable to store final answer
    ans = 0
 
    # Loop to find prefix-sum
    for i in range(1,n):
        arr[i] += arr[i - 1]
        if (arr[i] > k or arr[i] < -1 * k):
            ans+=1
 
    if (arr[0] > k or arr[0] < -1 * k):
        ans+=1
 
    # Sorting prefix-sum array
    arr=sorted(arr)
 
    # Loop to find upper_bound
    # for each element
    for i in range(n):
        ans += n - upper_bound(arr,arr[i] + k)
 
    # Returning final answer
    return ans
 
 
# Driver code
 
arr = [-1, 4, -5, 6]
n = len(arr)
k = 0
 
# Function to find required value
print(findCnt(arr, n, k))
 
# This code is contributed by mohit kumar 29

<script>
 
// Javascript implementation of the above approach
var maxLen = 30;
 
function upper_bound(a, low, high, element)
    {
        while(low < high)
        {
            var middle = low + parseInt((high - low)/2);
            if(a[middle] > element)
                high = middle;
            else
                low = middle + 1;
        }
        return low;
    }
 
// Function to find required value
function findCnt(arr, n, k)
{
    // Variable to store final answer
    var ans = 0;
 
    // Loop to find prefix-sum
    for (var i = 1; i < n; i++) {
        arr[i] += arr[i - 1];
        if (arr[i] > k || arr[i] < -1 * k)
            ans++;
    }
 
    if (arr[0] > k || arr[0] < -1 * k)
        ans++;
 
    // Sorting prefix-sum array
    arr.sort((a,b)=>a-b)
 
    // Loop to find upper_bound
    // for each element
    for (var i = 0; i < n; i++)
        ans += (n - upper_bound(arr, 0, n, arr[i] + k));
 
    // Returning final answer
    return ans;
}
 
// Driver code
var arr = [ -1, 4, -5, 6 ];
var n = arr.length;
var k = 0;
// Function to find required value
document.write( findCnt(arr, n, k));
 
 
</script>

10

Complejidad del tiempo : O(Nlog(N))