Given an array arr[] of size N, find a new array ans[] where each index i represents the absolute difference between the sum of elements to the left and right of index i in the array arr. Specifically,
ans[i] = |leftSum[i] – rightSum[i]|, where leftSum[i] is the sum of all elements to the left of index i and rightSum[i] is the sum of all elements to the right of index i.
Examples:
Input: arr[] = [10, 4, 8, 3], N = 4
Output: [15, 1, 11, 22]
Explanation: The array leftSum is [0, 10, 14, 22] and the array rightSum is [15, 11, 3, 0]. The array ans is [|0 – 15|, |10 – 11|, |14 – 3|, |22 – 0|] = [15, 1, 11, 22].Input: arr[] = [5], N =1
Output: [0]
Explanation: The array leftSum is [0] and the array rightSum is [0]. The array answer is [|0 – 0|] = [0].
Approach 1: Bruteforce approach
The brute force approach calculates the absolute difference between the left and right subarrays of each element in the input array by iterating through the array and summing the elements to the left and right of each element separately. This approach has a time complexity of O(N^2), where N is the size of the input array.
Below are the steps involved in the implementation of the code:
1. Create an empty list res to store the absolute difference for each element of the input array.
2. Iterate through the input array arr, and for each element arr[i], do the following:
2.1 Create two variables leftSum and rightSum, both initialized to 0. These variables will store the sum of the elements to the left and to the right of the current element, respectively.
2.2 Calculate the left sum by iterating from the first element of the array up to arr[i]-1 and adding each element to leftSum.
2.3 Calculate the right sum by iterating from arr[i]+1 up to the last element of the array and adding each element to rightSum.
2.4 Calculate the absolute difference between leftSum and rightSum using Math.abs(leftSum – rightSum).
2.5 Add the absolute difference to the result list res.
3. Return the result list res.
Below is the implementation for the above approach:
C++
#include <iostream>#include <vector>#include <cmath>using namespace std;vector<int> leftRightDifference(vector<int> arr){ int n = arr.size(); vector<int> res(n); for (int i = 0; i < n; i++) { int leftSum = 0, rightSum = 0; for (int j = 0; j < i; j++) leftSum += arr[j]; for (int j = i + 1; j < n; j++) rightSum += arr[j]; res[i] = abs(leftSum - rightSum); } return res;}int main(){ int N = 4; vector<int> arr = {10, 4, 8, 3}; vector<int> ans = leftRightDifference(arr); for (int i = 0; i < N; i++) cout << ans[i] << " "; return 0;} |
Java
import java.util.*;public class GFG { // Function to find absolute difference // between left and right variable public static List<Integer> leftRightDifference(List<Integer> arr) { int n = arr.size(); List<Integer> res = new ArrayList<Integer>(n); // Iterate in array arr[] for (int i = 0; i < n; i++) { int leftSum = 0, rightSum = 0; // calculate left sum for (int j = 0; j < i; j++) leftSum += arr.get(j); // calculate right sum for (int j = i + 1; j < n; j++) rightSum += arr.get(j); // add absolute difference to result list res.add(Math.abs(leftSum - rightSum)); } return res; } // Driver code public static void main(String[] args) { int N = 4; List<Integer> arr = new ArrayList<Integer>( Arrays.asList(10, 4, 8, 3)); // Function call List<Integer> ans = leftRightDifference(arr); for (int i = 0; i < N; i++) System.out.print(ans.get(i) + " "); }} |
Python3
# Function to find absolute difference# between left and right variabledef left_right_difference(arr): n = len(arr) res = [] # Iterate in array arr[] for i in range(n): left_sum = 0 right_sum = 0 # calculate left sum for j in range(i): left_sum += arr[j] # calculate right sum for j in range(i + 1, n): right_sum += arr[j] # add absolute difference to result list res.append(abs(left_sum - right_sum)) return res# Driver codeif __name__ == "__main__": N = 4 arr = [10, 4, 8, 3] # Function call ans = left_right_difference(arr) for i in range(N): print(ans[i], end=" ") |
C#
using System;using System.Collections.Generic;public class GFG{ public static List<int> LeftRightDifference(List<int> arr) { int n = arr.Count; // List to store absolute difference List<int> res = new List<int>(n); for (int i = 0; i < n; i++) { // This variable store left and right of array int leftSum = 0, rightSum = 0; // Calculating left sum for (int j = 0; j < i; j++) leftSum += arr[j]; // Caulculating right sum for (int j = i + 1; j < n; j++) rightSum += arr[j]; // Calculating absolute difference res.Add(Math.Abs(leftSum - rightSum)); } return res; } // Driver code public static void Main() { int N = 4; List<int> arr = new List<int> {10, 4, 8, 3}; List<int> ans = LeftRightDifference(arr); for (int i = 0; i < N; i++) Console.Write(ans[i] + " "); }} |
Javascript
function leftRightDifference(arr) { var n = arr.length; var res = new Array(n); for (var i = 0; i < n; i++) { var leftSum = 0, rightSum = 0; for (var j = 0; j < i; j++) leftSum += arr[j]; for (var j = i + 1; j < n; j++) rightSum += arr[j]; res[i] = Math.abs(leftSum - rightSum); } return res;}var N = 4;var arr = [10, 4, 8, 3];var ans = leftRightDifference(arr);for (var i = 0; i < N; i++) console.log(ans[i] + " "); |
15 1 11 22
Time complexity: O(N^2)
Auxiliary Space: O(1)
Approach 2 : This can be solved with the following idea:
Calculate the sum of all array arr[] in a variable. Iterate in the array and find the absolute difference between the left and right variables.
Below are the steps involved in the implementation of the code:
- Store the sum of the array by iterating.
- While iterating keep on adding the sum in the left variable.
- Find the absolute difference between sum and left and update in the array.
- Return the updated array arr.
Below is the implementation for the above approach:
C++
// C++ Implementation#include <bits/stdc++.h>using namespace std;// Function to find absolute difference// between left and right variablevector<int> leftRigthDifference(vector<int>& arr){ int n = arr.size(), left = 0, sum = 0, data; // Store the sum of array for (int i = 0; i < n; i++) sum += arr[i]; // Iterate in array arr[] for (int i = 0; i < n; i++) { left += arr[i]; data = abs(left - sum); sum -= arr[i]; // Update the array arr[i] = data; } return arr;}// Driver codeint main(){ int N = 4; vector<int> arr = { 10, 4, 8, 3 }; // Function call vector<int> ans = leftRigthDifference(arr); for (int i = 0; i < N; i++) cout << ans[i] << " "; return 0;} |
Java
// Java Implementationimport java.util.*;public class GFG { // Function to find absolute difference // between left and right variable public static List<Integer> leftRightDifference(List<Integer> arr) { int n = arr.size(), left = 0, sum = 0, data; List<Integer> res = new ArrayList<Integer>(n); // Store the sum of array for (int i = 0; i < n; i++) sum += arr.get(i); // Iterate in array arr[] for (int i = 0; i < n; i++) { left += arr.get(i); data = Math.abs(left - sum); sum -= arr.get(i); // Update the array res.add(data); } return res; } // Driver code public static void main(String[] args) { int N = 4; List<Integer> arr = new ArrayList<Integer>( Arrays.asList(10, 4, 8, 3)); // Function call List<Integer> ans = leftRightDifference(arr); for (int i = 0; i < N; i++) System.out.print(ans.get(i) + " "); }} |
Python3
def left_right_difference(arr): n = len(arr) left = 0 sum = 0 data = 0 for i in range(n): sum += arr[i] for i in range(n): left += arr[i] data = abs(left - sum) sum -= arr[i] arr[i] = data return arrN = 4arr = [10, 4, 8, 3]ans = left_right_difference(arr)for i in range(N): print(ans[i], end=" ") |
C#
using System;using System.Collections.Generic;public class Program{ // Function to find absolute difference // between left and right variable public static List<int> LeftRightDifference(List<int> arr) { int n = arr.Count; int left = 0; int sum = 0; int data; // Store the sum of array for (int i = 0; i < n; i++) sum += arr[i]; // Iterate in array arr[] for (int i = 0; i < n; i++) { left += arr[i]; data = Math.Abs(left - sum); sum -= arr[i]; // Update the array arr[i] = data; } return arr; } // Driver code public static void Main() { int N = 4; List<int> arr = new List<int> { 10, 4, 8, 3 }; List<int> ans = LeftRightDifference(arr); for (int i = 0; i < N; i++) Console.Write(ans[i] + " "); }} |
Javascript
// Function to find absolute difference// between left and right variablefunction leftRigthDifference(arr) { let n = arr.length; let left = 0; let sum = 0; let data;// Store the sum of array for (let i = 0; i < n; i++) { sum += arr[i]; }// Iterate in array arr[] for (let i = 0; i < n; i++) { left += arr[i]; data = Math.abs(left - sum); sum -= arr[i];// Update the array arr[i] = data; } return arr;}let N = 4;let arr = [10, 4, 8, 3];let ans = leftRigthDifference(arr);for (let i = 0; i < N; i++) { console.log(ans[i] + " ");} |
15 1 11 22
Time complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
