Number of subarrays having absolute sum greater than K | Set-2
Given an integer array arr[] of length N consisting of both positive and negative integers, the task is to find the number of sub-arrays with the absolute value of sum greater than a given positive number K.
Examples:
Input : arr[] = {-1, 0, 1}, K = 0
Output : 4
All possible sub-arrays and there total sum:
{-1} = -1
{0} = 0
{1} = 1
{-1, 0} = -1
{0, 1} = 1
{-1, 0, 1} = 0
Thus, 4 sub-arrays have absolute
value of sum greater than 0.Input : arr[] = {2, 3, 4}, K = 4
Output : 3
Approach: A similar approach that works on a positive integer array is discussed here.
In this article, we will look at an algorithm that solves this problem for both positive and negative integers.
- Create a prefix-sum array of the given array.
- Sort the prefix-sum array.
- Create variable ans, find the number of elements in the prefix-sum array with value lesser than -K or greater than K, and initialize ans with this value.
- Now, iterate the sorted prefix-sum array and for every index i, find the index of the first element with a value greater than arr[i] + K. Let’s say this index is j.
Then ans can be updated as ans += N – j as the number of elements in the prefix-sum array larger than the value of arr[i]+K will be equal to N – j.
To find the index j, perform binary search on prefix-sum array. Specifically, find the upper-bound on the value of prefix-sum[i] + k.
Below is the implementation of the above approach:
C++
// 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
// 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#
// 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
# 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 |
Javascript
<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
Time complexity : O(Nlog(N))
Auxiliary Space: O(1), no extra space is required, so it is a constant