Find the sum of all values lesser than the element of the Array
Given an array arr[] of n integers. For each index i, you have to find the sum of all integers present in the array with a value less than arr[i].
Examples:
Input: n = 3, arr[ ] = {1, 2, 3}
Output: 0 1 3
Explanation:
- For 1, there are no elements lesser than itself.
- For 2, only 1 is lesser than 2.
- And for 3, 1 and 2 are lesser than 3, so the sum is 3.
Input: n = 2, arr[] = {4, 4}
Output: 0 0
Explanation:
- For 4, there are no elements lesser than itself.
- For 4, there are no elements lesser than itself.
- There are no smaller elements than 4.
Approach 1: Bruteforce Approach
To solve the problem follow the below idea:
Use the first loop for traversing over array element and another loop is for calculating the sum of smaller elements.
- The first loop is for traversing the array elements.
- Store the sum of the smaller element by iterating again in the array using another loop.
- While iterating keep on adding the smaller elements in the sum variable.
- Print the updated array res.
Below are the steps for the above approach:
C++
// C++ code for above appraoch #include <bits/stdc++.h> using namespace std; // Function to calculate the smaller sum void SmallerSum( int n, vector< int >& arr) { // Declaration of result array which contains smaller // sum for each element vector< int > res(n); for ( int i = 0; i < n; i++) { int sum = 0; for ( int j = 0; j < n; j++) { if (arr[j] < arr[i]) sum += arr[j]; } res[i] = sum; } for ( int i = 0; i < n; i++) cout << res[i] << " " ; } // Driver code int main() { int n = 3; vector< int > arr = { 1, 2, 3 }; // Function call SmallerSum(n, arr); return 0; } |
Java
// Java Implementation import java.util.*; class GFG { // Function to calculate the smaller sum public static void SmallerSum( int n, List<Integer> arr) { // Declaration of result array which contains // smaller sum for each element List<Integer> res = new ArrayList<Integer>(n); for ( int i = 0 ; i < n; i++) { int sum = 0 ; for ( int j = 0 ; j < n; j++) { if (arr.get(j) < arr.get(i)) sum += arr.get(j); } // Update the array res.add(sum); } for ( int i = 0 ; i < n; i++) System.out.print(res.get(i) + " " ); } public static void main(String[] args) { int n = 3 ; List<Integer> arr = new ArrayList<Integer>( Arrays.asList( 1 , 2 , 3 )); // Function call SmallerSum(n, arr); } } |
Python3
# Python code for above appraoch def SmallerSum(n, arr): # Declaration of result list which contains # smaller sum for each element res = [] for i in range (n): # Initialize sum to 0 for each element sum = 0 for j in range (n): if arr[j] < arr[i]: sum + = arr[j] res.append( sum ) for i in range (n): print (res[i], end = " " ) # Driver code if __name__ = = "__main__" : n = 3 arr = [ 1 , 2 , 3 ] # Function call SmallerSum(n, arr) |
C#
// C# code for the above approach using System; using System.Collections.Generic; class GFG { // Function to calculate the smaller sum public static void SmallerSum( int n, List< int > arr) { // Declaration of result array which contains // smaller sum for each element List< int > res = new List< int >(); for ( int i = 0; i < n; i++) { int sum = 0; for ( int j = 0; j < n; j++) { if (arr[j] < arr[i]) sum += arr[j]; } // Update the array res.Add(sum); } for ( int i = 0; i < n; i++) Console.Write(res[i] + " " ); } public static void Main() { int n = 3; List< int > arr = new List< int >() {1, 2, 3}; // Function call SmallerSum(n, arr); } } // This code is contributed by Vaibhav Nandan |
Javascript
// Javascript code for above appraoch function calculateSmallerSum(n, arr) { // Declaration of result array which contains smaller // sum for each element let res = new Array(n); for (let i = 0; i < n; i++) { let sum = 0; for (let j = 0; j < n; j++) { if (arr[j] < arr[i]) { sum += arr[j]; } } res[i] = sum; } for (let i = 0; i < n; i++) { process.stdout.write(res[i] + " " ); } console.log(); } // Driver code function main() { let n = 3; let arr = [1, 2, 3]; // Function call calculateSmallerSum(n, arr); } main(); //this code is contributed by uttamdp_10 |
0 1 3
Time complexity: O(N^2)
Auxiliary Space: O(1)
Approach 2: This can be solved with the following idea:
Using HashMap it can be solved, where for each index find the index of element and check the sum of elements lesser than it.
Below is the implementation of the code:
- Take the input as size “n” and array “arr” and call the SmallerSum() function.
- The function creates an empty unordered_map “mp” that will be used to store the sum of all the elements smaller than a given element in the input vector.
- Creates a copy of the vector “arr” to “vec” and sorts “arr” in ascending order.
- Calculates the cumulative sum of all elements in the sorted vector “arr” and stores the sum in an unordered_map only if the current element is different from the previous element, ensuring that the sum is only calculated once for each unique element in the input vector.
- Loops over the original input vector “vec” and prints out the corresponding sum from the unordered_map for each element.
Below is the implementation of the above approach:
C++
// C++ code for above appraoch #include <bits/stdc++.h> using namespace std; // Function to calculate the smaller sum void SmallerSum( int n, vector< int >& arr) { // Create a hash map to store the // elements and their smaller sum unordered_map< int , long long int > mp; // Take a new vector to store original // vector "arr". vector< int > vec; vec = arr; // sort the arr vector in // ascending order sort(arr.begin(), arr.end()); // Variable to store the sum long long int sum = 0; // Variable to store previous element int pre = 0; for ( int i = 0; i < n; i++) { // If pre!=current then add // into map mp if (pre != arr[i]) mp[arr[i]] = sum; sum += arr[i]; pre = arr[i]; } // Print the answer according // to the original vector for ( int i = 0; i < n; i++) { cout << mp[vec[i]] << " " ; } cout << endl; } // Driver code int main() { int n = 3; vector< int > arr = { 1, 2, 3 }; // Function call SmallerSum(n, arr); n = 20; arr = { 0, 7, 7, 9, 0, 0, 5, 1, 0, 6, 6, 5, 8, 9, 9, 9, 1, 2, 4, 3 }; // Function call SmallerSum(n, arr); return 0; } |
Java
// Java code for above appraoch import java.util.*; public class SmallerSum { // Function to calculate the smaller sum static void calculateSmallerSum( int n, List<Integer> arr) { // Create a hash map to store the elements and their smaller sum, initialized with 0 Map<Integer, Long> mp = new HashMap<>(); for ( int element : arr) { mp.put(element, 0L); } // Take a new list to store the original list "arr". List<Integer> vec = new ArrayList<>(arr); // Sort the arr list in ascending order Collections.sort(arr); // Variable to store the sum long sum = 0 ; // Variable to store the previous element int pre = 0 ; for ( int i = 0 ; i < n; i++) { // If pre is not equal to the current element, add it to the map mp if (pre != arr.get(i)) { mp.put(arr.get(i), sum); } sum += arr.get(i); pre = arr.get(i); } // Print the answer according to the original list for ( int i = 0 ; i < n; i++) { System.out.print(mp.get(vec.get(i)) + " " ); } System.out.println(); } // Driver code public static void main(String[] args) { int n = 3 ; List<Integer> arr = new ArrayList<>(Arrays.asList( 1 , 2 , 3 )); // Function call calculateSmallerSum(n, arr); n = 20 ; arr = new ArrayList<>(Arrays.asList( 0 , 7 , 7 , 9 , 0 , 0 , 5 , 1 , 0 , 6 , 6 , 5 , 8 , 9 , 9 , 9 , 1 , 2 , 4 , 3 )); // Function call calculateSmallerSum(n, arr); } } // this code is contributed by uttamdp_10 |
Python3
#Python code for above appraoch def smaller_sum(n, arr): # Create a dictionary to store the elements and their smaller sum mp = {} # Take a new list to store the original list "arr" vec = list (arr) # Sort the arr list in ascending order arr.sort() # Variable to store the sum sum = 0 # Variable to store the previous element pre = None for i in range (n): # If pre != current, add it to the dictionary mp if pre ! = arr[i]: mp[arr[i]] = sum sum + = arr[i] pre = arr[i] # Print the answer according to the original list for i in range (n): print (mp[vec[i]], end = " " ) print () # Driver code if __name__ = = "__main__" : n = 3 arr = [ 1 , 2 , 3 ] # Function call smaller_sum(n, arr) n = 20 arr = [ 0 , 7 , 7 , 9 , 0 , 0 , 5 , 1 , 0 , 6 , 6 , 5 , 8 , 9 , 9 , 9 , 1 , 2 , 4 , 3 ] # Function call smaller_sum(n, arr) |
C#
//C# code for above appraoch using System; using System.Collections.Generic; using System.Linq; public class SmallerSum { // Function to calculate the smaller sum static void CalculateSmallerSum( int n, List< int > arr) { // Create a dictionary to store the elements and their smaller sum, initialized with 0 Dictionary< int , long > dict = new Dictionary< int , long >(); foreach ( int element in arr) { dict[element] = 0L; } // Take a new list to store the original list "arr". List< int > vec = new List< int >(arr); // Sort the arr list in ascending order arr.Sort(); // Variable to store the sum long sum = 0; // Variable to store the previous element int pre = 0; for ( int i = 0; i < n; i++) { // If pre is not equal to the current element, add it to the dictionary dict if (pre != arr[i]) { dict[arr[i]] = sum; } sum += arr[i]; pre = arr[i]; } // Print the answer according to the original list for ( int i = 0; i < n; i++) { Console.Write(dict[vec[i]] + " " ); } Console.WriteLine(); } // Driver code public static void Main( string [] args) { int n = 3; List< int > arr = new List< int > { 1, 2, 3 }; // Function call CalculateSmallerSum(n, arr); n = 20; arr = new List< int > { 0, 7, 7, 9, 0, 0, 5, 1, 0, 6, 6, 5, 8, 9, 9, 9, 1, 2, 4, 3 }; // Function call CalculateSmallerSum(n, arr); } } |
Javascript
function GFG(n, arr) { // Create an object to store the elements and // their smaller sum const mp = {}; // Copy the original array "arr" to // new array "vec" const vec = [...arr]; // Sort the "arr" array in ascending order arr.sort((a, b) => a - b); // Variable to store the sum let sum = 0; // Variable to store previous element let pre = 0; for (let i = 0; i < n; i++) { // If pre is not equal to the current element // add it to the object "mp" if (pre !== arr[i]) { mp[arr[i]] = sum; } sum += arr[i]; pre = arr[i]; } // Print the answer according to // original array "vec" for (let i = 0; i < n; i++) { process.stdout.write((mp[vec[i]] || 0) + " " ); } process.stdout.write( "\n" ); } // Driver code function main() { let n = 3; let arr = [1, 2, 3]; // Function call GFG(n, arr); n = 20; arr = [0, 7, 7, 9, 0, 0, 5, 1, 0, 6, 6, 5, 8, 9, 9, 9, 1, 2, 4, 3]; // Function call GFG(n, arr); } // Invoke the main function main(); |
0 1 3 0 33 33 55 0 0 11 0 0 21 21 11 47 55 55 55 0 2 7 4
Time Complexity: O(n*logn)
Auxiliary Space: O(n)