Count array elements exceeding sum of preceding K elements
Given an array arr[] of size N, and an integer K, the task is to find the count of array elements arr[i] which are greater than (arr[i – 1] + arr[i – 2] + … + arr[ i – K]).
Examples:
Input: arr[] = {2, 3, 8, 10, -2, 7, 5, 5, 9, 15}, K = 2
Output: 2
Explanation:
arr[2](> arr[1] + arr[0]) and arr[9](> arr[8] + arr[7]) are the two array elements exceeding sum of preceding K(= 2) elements.Input: arr[] = {17, -2, 16, -8, 19, 11, 5, 15, -9, 24}, K = 3
Output: 2
Approach: Follow the steps below to solve the problem:
- Calculate and store the prefix sum of the given array.
- Traverse the array elements present in the indices [K, N – 1].
- For every array element, check if arr[i] exceeds (arr[i – 1] + arr[i – 2] + … + arr[i – K]) or not. Therefore, the task is to check if arr[i] exceeds prefix[i – 1] – prefix[i – (K + 1)] for K > i > N or if arr[i] exceeds prefix[i – 1] for i = K.
- Increment count for array element satisfying the above conditions. Finally, print the required count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count array elements // exceeding sum of preceding K elements int countPrecedingK( int a[], int n, int K) { int prefix[n]; prefix[0] = a[0]; // Iterate over the array for ( int i = 1; i < n; i++) { // Update prefix sum prefix[i] = prefix[i - 1] + a[i]; } int ctr = 0; // Check if arr[K] > // arr[0] + .. + arr[K - 1] if (prefix[K - 1] < a[K]) // Increment count ctr++; for ( int i = K + 1; i < n; i++) { // Check if arr[i] > // arr[i - K - 1] + .. + arr[i - 1] if (prefix[i - 1] - prefix[i - K - 1] < a[i]) // Increment count ctr++; } return ctr; } // Driver Code int main() { // Given array int arr[] = { 2, 3, 8, 10, -2, 7, 5, 5, 9, 15 }; int N = sizeof (arr) / sizeof (arr[0]); int K = 2; cout << countPrecedingK(arr, N, K); return 0; } |
Java
// Java program for the above approach class GFG{ // Function to count array elements // exceeding sum of preceding K elements static int countPrecedingK( int a[], int n, int K) { int []prefix = new int [n]; prefix[ 0 ] = a[ 0 ]; // Iterate over the array for ( int i = 1 ; i < n; i++) { // Update prefix sum prefix[i] = prefix[i - 1 ] + a[i]; } int ctr = 0 ; // Check if arr[K] > // arr[0] + .. + arr[K - 1] if (prefix[K - 1 ] < a[K]) // Increment count ctr++; for ( int i = K + 1 ; i < n; i++) { // Check if arr[i] > // arr[i - K - 1] + .. + arr[i - 1] if (prefix[i - 1 ] - prefix[i - K - 1 ] < a[i]) // Increment count ctr++; } return ctr; } // Driver Code public static void main(String[] args) { // Given array int arr[] = { 2 , 3 , 8 , 10 , - 2 , 7 , 5 , 5 , 9 , 15 }; int N = arr.length; int K = 2 ; System.out.print(countPrecedingK(arr, N, K)); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function to count array elements # exceeding sum of preceding K elements def countPrecedingK(a, n, K): prefix = [ 0 ] * n prefix[ 0 ] = a[ 0 ] # Iterate over the array for i in range ( 1 , n): # Update prefix sum prefix[i] = prefix[i - 1 ] + a[i] ctr = 0 # Check if arr[K] > # arr[0] + .. + arr[K - 1] if (prefix[K - 1 ] < a[K]): # Increment count ctr + = 1 for i in range (K + 1 , n): # Check if arr[i] > # arr[i - K - 1] + .. + arr[i - 1] if (prefix[i - 1 ] - prefix[i - K - 1 ] < a[i]): # Increment count ctr + = 1 return ctr # Driver Code if __name__ = = '__main__' : # Given array arr = [ 2 , 3 , 8 , 10 , - 2 , 7 , 5 , 5 , 9 , 15 ] N = len (arr) K = 2 print (countPrecedingK(arr, N, K)) # This code is contributed by mohit kumar 29 |
C#
// C# program for // the above approach using System; class GFG{ // Function to count array elements // exceeding sum of preceding K elements static int countPrecedingK( int []a, int n, int K) { int []prefix = new int [n]; prefix[0] = a[0]; // Iterate over the array for ( int i = 1; i < n; i++) { // Update prefix sum prefix[i] = prefix[i - 1] + a[i]; } int ctr = 0; // Check if arr[K] > // arr[0] + .. + arr[K - 1] if (prefix[K - 1] < a[K]) // Increment count ctr++; for ( int i = K + 1; i < n; i++) { // Check if arr[i] > // arr[i - K - 1] + .. + arr[i - 1] if (prefix[i - 1] - prefix[i - K - 1] < a[i]) // Increment count ctr++; } return ctr; } // Driver Code public static void Main(String[] args) { // Given array int []arr = {2, 3, 8, 10, -2, 7, 5, 5, 9, 15}; int N = arr.Length; int K = 2; Console.Write(countPrecedingK(arr, N, K)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript program to implement // the above approach // Function to count array elements // exceeding sum of preceding K elements function countPrecedingK(a, n, K) { let prefix = new Array(n).fill(0); prefix[0] = a[0]; // Iterate over the array for (let i = 1; i < n; i++) { // Update prefix sum prefix[i] = prefix[i - 1] + a[i]; } let ctr = 0; // Check if arr[K] > // arr[0] + .. + arr[K - 1] if (prefix[K - 1] < a[K]) // Increment count ctr++; for (let i = K + 1; i < n; i++) { // Check if arr[i] > // arr[i - K - 1] + .. + arr[i - 1] if (prefix[i - 1] - prefix[i - K - 1] < a[i]) // Increment count ctr++; } return ctr; } // Driver Code // Given array let arr = [ 2, 3, 8, 10, -2, 7, 5, 5, 9, 15 ]; let N = arr.length; let K = 2; document.write(countPrecedingK(arr, N, K)); </script> |
Output:
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us