Sum of previous numbers that are greater than current number for given array

0 0 10 minutes read

Given an array A[], for each element in the array, the task is to find the sum of all the previous elements which are strictly greater than the current element.

Examples:

Input: A[] = {2, 6, 4, 1, 7}
Output: 0 0 6 12 0
Explanation:
For 2 and 6 there is no element greater to it on the left.
For 4 there is 6.
For 1 the sum would be 12.
For 7 there is again no element greater to it.

Input: A[] = {7, 3, 6, 2, 1}
Output: 0 7 7 16 18
Explanation:
For 7 there is no element greater to it on the left.
For 3 there is 7.
For 6 the sum would be 7.
For 2 it has to be 7 + 3 + 6 = 16.
For 1 the sum would be 7 + 3 + 6 + 2 = 18

Naive Approach: For each element, the idea is to find the elements which are strictly greater than the current element on the left side of it and then find the sum of all those elements.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Max Element of the Array
const int maxn = 1000000;
 
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
void sumGreater(int ar[], int N)
{
 
    // Loop to iterate over all
    // the elements of the array
    for (int i = 0; i < N; i++) {
 
        // Store the answer for
        // the current element
        int cur_sum = 0;
 
        // Iterate from (current index - 1)
        // to 0 and check if ar[j] is greater
        // than the current element and add
        // it to the cur_sum if so
 
        for (int j = i - 1; j >= 0; j--) {
 
            if (ar[j] > ar[i])
                cur_sum += ar[j];
        }
 
        // Print the answer for
        // current element
        cout << cur_sum << " ";
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int ar[] = { 7, 3, 6, 2, 1 };
 
    // Size of the array
    int N = sizeof ar / sizeof ar[0];
 
    // Function call
    sumGreater(ar, N);
    return 0;
}

Java

// Java program for the above approach
class GFG{
 
// Max Element of the Array
static int maxn = 1000000;
 
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
static void sumGreater(int ar[], int N)
{
     
    // Loop to iterate over all
    // the elements of the array
    for(int i = 0; i < N; i++)
    {
         
        // Store the answer for
        // the current element
        int cur_sum = 0;
 
        // Iterate from (current index - 1)
        // to 0 and check if ar[j] is greater
        // than the current element and add
        // it to the cur_sum if so
        for(int j = i - 1; j >= 0; j--)
        {
            if (ar[j] > ar[i])
                cur_sum += ar[j];
        }
 
        // Print the answer for
        // current element
        System.out.print(cur_sum + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given array arr[]
    int ar[] = { 7, 3, 6, 2, 1 };
 
    // Size of the array
    int N = ar.length;
 
    // Function call
    sumGreater(ar, N);
}
}
 
// This code is contributed by amal kumar choubey

Python3

# Python3 program for the above approach
 
# Max Element of the Array
maxn = 1000000;
 
# Function to find the sum of previous
# numbers that are greater than the
# current number for the given array
def sumGreater(ar, N):
 
    # Loop to iterate over all
    # the elements of the array
    for i in range(N):
 
        # Store the answer for
        # the current element
        cur_sum = 0;
 
        # Iterate from (current index - 1)
        # to 0 and check if ar[j] is greater
        # than the current element and add
        # it to the cur_sum if so
        for j in range(i, -1, -1):
            if (ar[j] > ar[i]):
                cur_sum += ar[j];
         
        # Print the answer for
        # current element
        print(cur_sum, end = " ");
     
# Driver Code
if __name__ == '__main__':
 
    # Given array arr
    ar = [ 7, 3, 6, 2, 1] ;
 
    # Size of the array
    N = len(ar);
 
    # Function call
    sumGreater(ar, N);
 
# This code is contributed by sapnasingh4991

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Max Element of the Array
//static int maxn = 1000000;
 
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
static void sumGreater(int []ar, int N)
{
     
    // Loop to iterate over all
    // the elements of the array
    for(int i = 0; i < N; i++)
    {
         
        // Store the answer for
        // the current element
        int cur_sum = 0;
 
        // Iterate from (current index - 1)
        // to 0 and check if ar[j] is greater
        // than the current element and add
        // it to the cur_sum if so
        for(int j = i - 1; j >= 0; j--)
        {
            if (ar[j] > ar[i])
                cur_sum += ar[j];
        }
 
        // Print the answer for
        // current element
        Console.Write(cur_sum + " ");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Given array []arr
    int []ar = { 7, 3, 6, 2, 1 };
 
    // Size of the array
    int N = ar.Length;
 
    // Function call
    sumGreater(ar, N);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program for the above approach    
// Max Element of the Array
var maxn = 1000000;
 
// Function to find the sum of previous
// numbers that are greater than the
// current number for the given array
function sumGreater(ar, N)
{
     
    // Loop to iterate over all
    // the elements of the array
    for(i = 0; i < N; i++) 
    {
         
        // Store the answer for
        // the current element
        var cur_sum = 0;
 
        // Iterate from (current index - 1)
        // to 0 and check if ar[j] is greater
        // than the current element and add
        // it to the cur_sum if so
        for(j = i - 1; j >= 0; j--) 
        {
            if (ar[j] > ar[i])
                cur_sum += ar[j];
        }
 
        // Print the answer for
        // current element
        document.write(cur_sum + " ");
    }
}
 
// Driver Code
 
// Given array arr
var ar = [ 7, 3, 6, 2, 1 ];
 
// Size of the array
var N = ar.length;
 
// Function call
sumGreater(ar, N);
 
// This code is contributed by umadevi9616
 
</script>

Output:

0 7 7 16 18

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach the idea is to use Fenwick Tree. Below are the steps:

Traverse the given array and find the sum(say total_sum) of all the elements stored in the Fenwick Tree.
Now Consider each element(say arr[i]) as the index of the Fenwick Tree.
Now find the sum of all the elements(say curr_sum) which is smaller than the current element using values stored in Tree.
The value of total_sum – curr_sum will give the sum of all elements which are strictly greater than the elements on the left side of the current element.
Update the current element in the Fenwick Tree.
Repeat the above steps for all the elements in the array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Max Element of the Array
const int maxn = 1000000;
 
// Initializing Fenwick Tree
int Bit[maxn + 5];
 
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
void sum(int ar[], int N)
{
 
    // Iterate from 1 to N
    for (int i = 0; i < N; i++) {
        int index;
        int total_sum = 0;
        index = 100000;
 
        // If some greater values has
        // occurred before current element
        // then it will be already stored
        // in Fenwick Tree
        while (index) {
 
            // Calculating sum of
            // all the elements
            total_sum += Bit[index];
            index -= index & -index;
        }
        int cur_sum = 0;
 
        // Sum only smaller or equal
        // elements than current element
        index = ar[i];
 
        while (index) {
 
            // If some smaller values has
            // occurred before it will be
            // already stored in Tree
            cur_sum += Bit[index];
            index -= (index & -index);
        }
 
        int ans = total_sum - cur_sum;
        cout << ans << " ";
 
        // Update the fenwick tree
        index = ar[i];
        while (index <= 100000) {
 
            // Updating The Fenwick Tree
            // for future values
            Bit[index] += ar[i];
            index += (index & -index);
        }
    }
}
 
// Driver Code
int main()
{
    // Given array arr[]
    int ar[] = { 7, 3, 6, 2, 1 };
    int N = sizeof ar / sizeof ar[0];
 
    // Function call
    sum(ar, N);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
class GFG{
 
// Max Element of the Array
static int maxn = 1000000;
 
// Initializing Fenwick Tree
static int []Bit = new int[maxn + 5];
 
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
static void sum(int ar[], int N)
{
 
    // Iterate from 1 to N
    for (int i = 0; i < N; i++) 
    {
        int index;
        int total_sum = 0;
        index = 100000;
 
        // If some greater values has
        // occurred before current element
        // then it will be already stored
        // in Fenwick Tree
        while (index > 0)
        {
 
            // Calculating sum of
            // all the elements
            total_sum += Bit[index];
            index -= index & -index;
        }
        int cur_sum = 0;
 
        // Sum only smaller or equal
        // elements than current element
        index = ar[i];
 
        while (index > 0)
        {
 
            // If some smaller values has
            // occurred before it will be
            // already stored in Tree
            cur_sum += Bit[index];
            index -= (index & -index);
        }
 
        int ans = total_sum - cur_sum;
        System.out.print(ans + " ");
 
        // Update the fenwick tree
        index = ar[i];
        while (index <= 100000) 
        {
 
            // Updating The Fenwick Tree
            // for future values
            Bit[index] += ar[i];
            index += (index & -index);
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    // Given array arr[]
    int ar[] = { 7, 3, 6, 2, 1 };
    int N = ar.length;
 
    // Function call
    sum(ar, N);
}
}
 
// This code is contributed by Rohit_ranjan

Python3

# Python3 program for the above approach
 
# Max Element of the Array
maxn = 1000000;
 
# Initializing Fenwick Tree
Bit = [0] * (maxn + 5);
 
# Function to calculate the sum of
# previous numbers that are greater
# than the current number in the array
def sum(ar, N):
   
    # Iterate from 1 to N
    for i in range(N):
        total_sum = 0;
        index = 100000;
 
        # If some greater values has
        # occurred before current element
        # then it will be already stored
        # in Fenwick Tree
        while (index > 0):
           
            # Calculating sum of
            # all the elements
            total_sum += Bit[index];
            index -= index & -index;
 
        cur_sum = 0;
 
        # Sum only smaller or equal
        # elements than current element
        index = ar[i];
 
        while (index > 0):
           
            # If some smaller values has
            # occurred before it will be
            # already stored in Tree
            cur_sum += Bit[index];
            index -= (index & -index);
 
        ans = total_sum - cur_sum;
        print(ans, end=" ");
 
        # Update the fenwick tree
        index = ar[i];
        while (index <= 100000):
           
            # Updating The Fenwick Tree
            # for future values
            Bit[index] += ar[i];
            index += (index & -index);
 
# Driver Code
if __name__ == '__main__':
    # Given array arr
    arr = [7, 3, 6, 2, 1];
    N = len(arr);
 
    # Function call
    sum(arr, N);
 
# This code is contributed by sapnasingh4991

C#

// C# program for the above approach
using System;
class GFG{
 
// Max Element of the Array
static int maxn = 1000000;
 
// Initializing Fenwick Tree
static int []Bit = new int[maxn + 5];
 
// Function to calculate the sum of
// previous numbers that are greater
// than the current number in the array
static void sum(int []ar, int N)
{
 
    // Iterate from 1 to N
    for (int i = 0; i < N; i++) 
    {
        int index;
        int total_sum = 0;
        index = 100000;
 
        // If some greater values has
        // occurred before current element
        // then it will be already stored
        // in Fenwick Tree
        while (index > 0)
        {
 
            // Calculating sum of
            // all the elements
            total_sum += Bit[index];
            index -= index & -index;
        }
        int cur_sum = 0;
 
        // Sum only smaller or equal
        // elements than current element
        index = ar[i];
 
        while (index > 0)
        {
 
            // If some smaller values has
            // occurred before it will be
            // already stored in Tree
            cur_sum += Bit[index];
            index -= (index & -index);
        }
 
        int ans = total_sum - cur_sum;
        Console.Write(ans + " ");
 
        // Update the fenwick tree
        index = ar[i];
        while (index <= 100000) 
        {
 
            // Updating The Fenwick Tree
            // for future values
            Bit[index] += ar[i];
            index += (index & -index);
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    // Given array []arr
    int []ar = { 7, 3, 6, 2, 1 };
    int N = ar.Length;
 
    // Function call
    sum(ar, N);
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
// javascript program for the above approach
 
    // Max Element of the Array
    var maxn = 1000000;
 
    // Initializing Fenwick Tree
     var Bit = Array(maxn + 5).fill(0);
 
    // Function to calculate the sum of
    // previous numbers that are greater
    // than the current number in the array
    function sum(ar , N) {
 
        // Iterate from 1 to N
        for (i = 0; i < N; i++) {
            var index;
            var total_sum = 0;
            index = 100000;
 
            // If some greater values has
            // occurred before current element
            // then it will be already stored
            // in Fenwick Tree
            while (index > 0) {
 
                // Calculating sum of
                // all the elements
                total_sum += Bit[index];
                index -= index & -index;
            }
            var cur_sum = 0;
 
            // Sum only smaller or equal
            // elements than current element
            index = ar[i];
 
            while (index > 0) {
 
                // If some smaller values has
                // occurred before it will be
                // already stored in Tree
                cur_sum += Bit[index];
                index -= (index & -index);
            }
 
            var ans = total_sum - cur_sum;
            document.write(ans + " ");
 
            // Update the fenwick tree
            index = ar[i];
            while (index <= 100000) {
 
                // Updating The Fenwick Tree
                // for future values
                Bit[index] += ar[i];
                index += (index & -index);
            }
        }
    }
 
    // Driver Code
     
        // Given array arr
        var ar = [ 7, 3, 6, 2, 1 ];
        var N = ar.length;
 
        // Function call
        sum(ar, N);
 
// This code contributed by aashish1995
</script>

Output:

0 7 7 16 18

Time Complexity: O(N * log(max_element))
Auxiliary Space: O(max_element)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!