Given an array arr[] of integers of length N, the task is to find the product of the sum of all the numbers larger than that number with the sum of all the numbers less than that number for each number in the array.
Examples:
Input: arr[] = {8, 4, 9, 3}, N = 4
Output:- 63, 51, 0, 0
Explanation:
For first number 8: Sum of elements smaller than this is (4 + 3) = 7
and sum of elements greater than this is 9. hence output is 7*9 = 63.
For 4: Summation of elements smaller than this is 3 and
summation of elements greater than this is (9 + 8) = 17 hence output is 17*3 = 51
For 9: Summation of elements smaller than this is (8 + 4 + 3 ) = 15 and
summation of elements greater than this is 0. Hence output is 15*0 = 0
For 3: Summation of elements smaller than this is 0 and
summation of elements greater than this is (8 + 4 + 9) = 21. Hence output is 0*21 = 0Input: arr[] = {1, 4, 7, 3, 6}, N = 5
Output: 0, 52, 0, 17, 56
Approach: The idea is to find the sum of all the smaller elements and all the greater elements for each array element and then find the product for those.
Follow the steps below to solve this problem:
- Iterate through all the elements of an array.
- For each element of an array keep adding elements smaller than the current and elements greater than the current element in two different variables.
- Multiply these two variables ( i.e which are storing elements greater and less than the current element )
- Store the answer for each element.
- Return the array storing the answers.
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to find the answervector<int> constructArray(int arr[], int n){ int i, s = 0, j = 0, sum = 0; vector<int> v; for (i = 0; i < n; i++) { s = 0, sum = 0; for (j = 0; j < n; j++) { if (arr[j] != arr[i]) { // Addition of elements // greater than ith indexed // element if (arr[i] > arr[j]) s += arr[j]; // Addition of elements // less than ith indexed // element else sum += arr[j]; } } // Storing the product of elements // greater than ith indexed elements // with elements less than ith // indexed element. v.push_back(s * sum); } return v;}// Driver Codeint main(){ int N = 4; int arr[] = { 8, 4, 9, 3 }; // Function call vector<int> ans = constructArray(arr, N); for (int x : ans) cout << x << " "; return 0;} |
C
#include <stdio.h>#include <stdlib.h>// Function to find the answervoid constructArray(int arr[], int n){ int i, s = 0, j = 0, sum = 0; int idx=0; int v[n]; for (i = 0; i < n; i++) { s = 0, sum = 0; for (j = 0; j < n; j++) { if (arr[j] != arr[i]) { // Addition of elements // greater than ith indexed // element if (arr[i] > arr[j]) s += arr[j]; // Addition of elements // less than ith indexed // element else sum += arr[j]; } } // Storing the product of elements // greater than ith indexed elements // with elements less than ith // indexed element. v[idx++]=(s * sum); } for(int i=0;i<idx;i++){ printf("%d , ",v[i]); } }// Driver Codeint main(){ int N = 4; int arr[] = { 8, 4, 9, 3 }; // Function call constructArray(arr, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;import java.util.*;class GFG { // Function to find the answer public static ArrayList<Integer> constructArray(int arr[], int n) { int i = 0; int s = 0; int j = 0; int sum = 0; ArrayList<Integer> v = new ArrayList<Integer>(); for (i = 0; i < n; i++) { s = 0; sum = 0; for (j = 0; j < n; j++) { if (arr[j] != arr[i]) { // Addition of elements // greater than ith indexed // element if (arr[i] > arr[j]) s += arr[j]; // Addition of elements // less than ith indexed // element else sum += arr[j]; } } // Storing the product of elements // greater than ith indexed elements // with elements less than ith // indexed element. v.add(s * sum); } return v; } public static void main(String[] args) { int N = 4; int arr[] = { 8, 4, 9, 3 }; // Function call ArrayList<Integer> ans = constructArray(arr, N); for (Integer x : ans) System.out.print(x + " "); }}// This code is contributed by Rohit Pradhan |
Python3
# Python3 code to implement the approach# Function to find the answerdef constructArray(arr, n): s = 0 sums = 0 v = [] for i in range(n): s = 0 sums = 0 for j in range(n): if arr[j] != arr[i]: # Addition of elements # greater than ith indexed # element if arr[i] > arr[j]: s += arr[j] # Addition of elements # less than ith indexed # element else: sums += arr[j] # Storing the product of elements # greater than ith indexed elements # with elements less than ith # indexed element. v.append(s * sums) return v# Driver CodeN = 4arr = [8, 4, 9, 3]# Function Callans = constructArray(arr, N)print(" ".join(list(map(str, ans))))# this code is contributed by phasing17 |
C#
// C# code to implement the approachusing System;using System.Collections;public class GFG{ // Function to find the answer public static ArrayList constructArray(int[] arr, int n) { int i = 0; int s = 0; int j = 0; int sum = 0; ArrayList v = new ArrayList(); for (i = 0; i < n; i++) { s = 0; sum = 0; for (j = 0; j < n; j++) { if (arr[j] != arr[i]) { // Addition of elements // greater than ith indexed // element if (arr[i] > arr[j]) s += arr[j]; // Addition of elements // less than ith indexed // element else sum += arr[j]; } } // Storing the product of elements // greater than ith indexed elements // with elements less than ith // indexed element. v.Add(s * sum); } return v; } static public void Main (){ int N = 4; int[] arr = { 8, 4, 9, 3 }; // Function call ArrayList ans = constructArray(arr, N); foreach (var x in ans) Console.Write(x + " "); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script> // JavaScript code for the above approach // Function to find the answer function constructArray(arr, n) { let i, s = 0, j = 0, sum = 0; let v = []; for (i = 0; i < n; i++) { s = 0, sum = 0; for (j = 0; j < n; j++) { if (arr[j] != arr[i]) { // Addition of elements // greater than ith indexed // element if (arr[i] > arr[j]) s += arr[j]; // Addition of elements // less than ith indexed // element else sum += arr[j]; } } // Storing the product of elements // greater than ith indexed elements // with elements less than ith // indexed element. v.push(s * sum); } return v; } // Driver Code let N = 4; let arr = [8, 4, 9, 3]; // Function call let ans = constructArray(arr, N); for (let x of ans) document.write(x + " ") // This code is contributed by Potta Lokesh </script> |
Output
63 51 0 0
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach:
Above solution works in O(N2) time, we can write a solution in O(n*Logn) time and with O(N) space complexity.
The idea is to sort the array and finding prefix_sum of sorted array.Now prefix sum will help us in finding the sum of all smaller elements and sum of all larger elements of the current element.
Follow the steps below for understanding…
- sort the given array and store resultant array into another array
- find prefix_sum array of sorted array
- Now find index of each element of given array into sorted array using binary search.
- With the help of prefix array,we can directly calculate sum of all smaller element and sum of all larger element of the current element.
- to calculate the resultant value corresponding to each element, do smaller*larger.
finally return the array storing the answers
Below is the implementation of the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;int binary_search(vector<int> &arr, int low, int high, int x){ // Check base case if (high >= low) { int mid = ((high + low) / 2); // If element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it can only // be present in left subarray else if (arr[mid] > x) return binary_search(arr, low, mid - 1, x); // Else the element can only be present in right subarray else return binary_search(arr, mid + 1, high, x); }}vector<int> constructArray(vector<int> &arr, int n){ // sorting the arr and assigning to another array vector<int> arr2; arr2 = arr; sort(arr2.begin(),arr2.end()); // Initializing prefix_sum array int prefix_sum[n] = {0}; // first element of prefix_sum and given array will be the same prefix_sum[0] = arr2[0]; // iterating through 0 to n-1 and // calculating prefix_sum for (int i = 1; i < n; i++) prefix_sum[i] = prefix_sum[i - 1] + arr2[i]; int element_index, smaller, larger; for (int i = 0; i < n; i++) { // storing index of each element of given array // in our sorted array using binary search element_index = binary_search(arr2, 0, n - 1, arr[i]); // storing sum of all smaller elements into smaller smaller = prefix_sum[element_index] - arr[i]; // storing sum of all larger element into larger larger = prefix_sum[n - 1] - prefix_sum[element_index]; // multiplying smaller and larger and ' // storing into arr[i]' arr[i] = smaller * larger; } return arr;}// Driver Codeint main(){ int N = 4; vector<int> arr; arr.push_back(8); arr.push_back(4); arr.push_back(9); arr.push_back(3); // Function Call constructArray(arr, N); for (int i = 0; i < N; i++) { /* code */ cout << arr[i] << " "; } }// This code is contributed by adityamaharshi21. |
Java
import java.util.*;import java.io.*;// Java program for the above approachclass GFG{ static int binary_search(ArrayList<Integer> arr, int low, int high, int x){ // Check base case if (high >= low){ int mid = (high + low); // 2 // If element is present at the middle itself if (arr.get(mid) == x){ return mid; // If element is smaller than mid, then it can only // be present in left subarray }else if(arr.get(mid) > x){ return binary_search(arr, low, mid - 1, x); // Else the element can only be present in right subarray }else{ return binary_search(arr, mid + 1, high, x); } } return -1; } static ArrayList<Integer> constructArray(ArrayList<Integer> arr, int n){ // sorting the arr and assigning to another array ArrayList<Integer> arr2 = new ArrayList<Integer>(arr); Collections.sort(arr2); // Initializing prefix_sum array int[] prefix_sum = new int[n]; // first element of prefix_sum and given array will be the same prefix_sum[0] = arr2.get(0); // iterating through 0 to n-1 and // calculating prefix_sum for (int i = 1 ; i < n ; i++){ prefix_sum[i] = prefix_sum[i-1] + arr2.get(i); } for (int i = 0 ; i < n ; i++){ // storing index of each element of given array // in our sorted array using binary search int element_index = binary_search(arr2, 0, n - 1, arr.get(i)); // storing sum of all smaller elements into smaller int smaller = prefix_sum[element_index]-arr.get(i); // storing sum of all larger element into larger int larger = prefix_sum[n-1]-prefix_sum[element_index]; // multiplying smaller and larger and ' // storing into arr[i]' arr.set(i, smaller * larger); } return arr; } // Driver code public static void main(String args[]) { int N = 4; ArrayList<Integer> arr = new ArrayList<Integer>( List.of( 8, 4, 9, 3 ) ); // Function Call ArrayList<Integer> ans = constructArray(arr, N); for(int i = 0 ; i < ans.size() ; i++){ System.out.print(ans.get(i) + " "); } System.out.println(""); }}// This code is contributed by subhamgoyal2014. |
Python3
def binary_search(arr, low, high, x): # Check base case if high >= low: mid = (high + low) // 2 # If element is present at the middle itself if arr[mid] == x: return mid # If element is smaller than mid, then it can only # be present in left subarray elif arr[mid] > x: return binary_search(arr, low, mid - 1, x) # Else the element can only be present in right subarray else: return binary_search(arr, mid + 1, high, x)def constructArray(arr, n): # sorting the arr and assigning to another array arr2 = sorted(arr) # Initializing prefix_sum array prefix_sum = [0]*n # first element of prefix_sum and given array will be the same prefix_sum[0] = arr2[0] # iterating through 0 to n-1 and # calculating prefix_sum for i in range(1, n): prefix_sum[i] = prefix_sum[i-1]+arr2[i] for i in range(n): # storing index of each element of given array # in our sorted array using binary search element_index = binary_search(arr2, 0, n-1, arr[i]) # storing sum of all smaller elements into smaller smaller = prefix_sum[element_index]-arr[i] # storing sum of all larger element into larger larger = prefix_sum[n-1]-prefix_sum[element_index] # multiplying smaller and larger and ' # storing into arr[i]' arr[i] = smaller*larger return arr# Driver CodeN = 4arr = [8, 4, 9, 3]# Function Callans = constructArray(arr, N)print(" ".join(list(map(str, ans))))''' Code is written by RAJAT KUMAR ''' |
C#
// C# program to implement above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{ static int binary_search(List<int> arr, int low, int high, int x){ // Check base case if (high >= low){ int mid = (high + low); // 2 // If element is present at the middle itself if (arr[mid] == x){ return mid; // If element is smaller than mid, then it can only // be present in left subarray }else if(arr[mid] > x){ return binary_search(arr, low, mid - 1, x); // Else the element can only be present in right subarray }else{ return binary_search(arr, mid + 1, high, x); } } return -1; } static List<int> constructArray(List<int> arr, int n){ // sorting the arr and assigning to another array List<int> arr2 = new List<int>(arr); arr2.Sort(); // Initializing prefix_sum array int[] prefix_sum = new int[n]; // first element of prefix_sum and given array will be the same prefix_sum[0] = arr2[0]; // iterating through 0 to n-1 and // calculating prefix_sum for (int i = 1 ; i < n ; i++){ prefix_sum[i] = prefix_sum[i-1] + arr2[i]; } for (int i = 0 ; i < n ; i++){ // storing index of each element of given array // in our sorted array using binary search int element_index = binary_search(arr2, 0, n - 1, arr[i]); // storing sum of all smaller elements into smaller int smaller = prefix_sum[element_index]-arr[i]; // storing sum of all larger element into larger int larger = prefix_sum[n-1]-prefix_sum[element_index]; // multiplying smaller and larger and ' // storing into arr[i]' arr[i] = smaller * larger; } return arr; } // Driver code public static void Main(string[] args){ int N = 4; List<int> arr = new List<int>{8, 4, 9, 3}; // Function Call List<int> ans = constructArray(arr, N); for(int i = 0 ; i < ans.Count ; i++){ Console.Write(ans[i] + " "); } Console.WriteLine(""); }}// This code is contributed entertain2022. |
Javascript
// JavaScript code to implement the approachfunction binary_search(arr, low, high, x){ // Check base case if (high >= low) { let mid = Math.floor((high + low) / 2); // If element is present at the middle itself if (arr[mid] == x) return mid; // If element is smaller than mid, then it can only // be present in left subarray else if (arr[mid] > x) return binary_search(arr, low, mid - 1, x); // Else the element can only be present in right subarray else return binary_search(arr, mid + 1, high, x); }}function constructArray(arr, n){ // sorting the arr and assigning to another array let arr2 = [...arr]; arr2.sort(); // Initializing prefix_sum array prefix_sum = new Array(n).fill(0); // first element of prefix_sum and given array will be the same prefix_sum[0] = arr2[0]; // iterating through 0 to n-1 and // calculating prefix_sum for (var i = 1; i < n; i++) prefix_sum[i] = prefix_sum[i-1]+arr2[i]; let element_index, smaller, larger; for (var i = 0; i < n; i++) { // storing index of each element of given array // in our sorted array using binary search element_index = binary_search(arr2, 0, n-1, arr[i]); // storing sum of all smaller elements into smaller smaller = prefix_sum[element_index]-arr[i]; // storing sum of all larger element into larger larger = prefix_sum[n-1]-prefix_sum[element_index] // multiplying smaller and larger and ' // storing into arr[i]' arr[i] = smaller*larger; } return arr;}// Driver Codelet N = 4;let arr = [8, 4, 9, 3];// Function Calllet ans = constructArray(arr, N);console.log(ans);// This code is contributed by phasing17. |
Output
63 51 0 0
Time Complexity: Steps involved into time requirement:
- Sorting the array takes :O(n*log(n)) time
- Finding prefix sum takes O(n) time
- Calling binary_search function each time inside loop running n time : O(n*logn)
Overall Time Complexity: O(n*logn)
Auxiliary Space: O(n)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
