Replace all elements by difference of sums of positive and negative numbers after that element
Given an array of positive and negative elements. The task is to replace every i-th element of the array by the absolute difference of absolute sums of positive and negative elements in the range i+1 to N. That is, find the absolute sum of all positive elements and the absolute sum of all negative elements in the range i+1 to N. Now find the absolute difference between these two sums and replace it with the i-th element.
Note: The last element of the updated array will be zero.
Examples:
Input : N = 5, arr[] = {1, -1, 2, 3, -2}
Output : arr[] = {2, 3, 1, 2, 0}
Input : N = 6, arr[] = {-3, -4, -2, 5, 1, -2}
Output : arr[] = {2, 2, 4, 1, 2, 0}.
Naive Approach: The naive approach is to run two for loops and for all i-th elements, calculate abs value of the sum of all positive and negative elements with an index in the range i+1 to N. Now find the absolute difference of both sums and replace it with the i-th element.
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <iostream>using namespace std;// Function to print the array elementsvoid printArray(int N, int arr[]){ for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << endl;}// Function to replace all elements with absolute// difference of absolute sums of positive// and negative elementsvoid replacedArray(int N, int arr[]){ int pos_sum, neg_sum, i, j, diff; for (i = 0; i < N; i++) { pos_sum = 0; neg_sum = 0; // Calculate absolute sums of positive // and negative elements in range i+1 to N for (j = i + 1; j < N; j++) { if (arr[j] > 0) pos_sum += arr[j]; else neg_sum += arr[j]; } // calculate difference of both sums diff = abs(pos_sum) - abs(neg_sum); // replace i-th elements with absolute // difference arr[i] = abs(diff); }}// Driver codeint main(){ int N = 5; int arr[] = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int arr1[] = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1); return 0;} |
Java
// Java program to implement above approachclass GFG{ // Function to print the array elementsstatic void printArray(int N, int []arr){ for (int i = 0; i < N; i++) System.out.print(arr[i] + " "); System.out.println();}// Function to replace all elements with // absolute difference of absolute sums // of positive and negative elementsstatic void replacedArray(int N, int []arr){ int pos_sum, neg_sum, i, j, diff; for (i = 0; i < N; i++) { pos_sum = 0; neg_sum = 0; // Calculate absolute sums of positive // and negative elements in range i+1 to N for (j = i + 1; j < N; j++) { if (arr[j] > 0) pos_sum += arr[j]; else neg_sum += arr[j]; } // calculate difference of both sums diff = Math.abs(pos_sum) - Math.abs(neg_sum); // replace i-th elements with absolute // difference arr[i] = Math.abs(diff); }}// Driver codepublic static void main(String args[]){ int N = 5; int []arr = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int []arr1 = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1);}}// This code is contributed by Akanksha Rai |
Python3
# Python 3 program to implement # above approach# Function to print the array elementsdef printArray(N, arr): for i in range(N): print(arr[i], end = " ") print("\n", end = "")# Function to replace all elements with # absolute difference of absolute sums # of positive and negative elementsdef replacedArray(N, arr): for i in range(N): pos_sum = 0 neg_sum = 0 # Calculate absolute sums of positive # and negative elements in range i+1 to N for j in range(i + 1, N, 1): if (arr[j] > 0): pos_sum += arr[j] else: neg_sum += arr[j] # calculate difference of both sums diff = abs(pos_sum) - abs(neg_sum) # replace i-th elements with absolute # difference arr[i] = abs(diff)# Driver codeif __name__ == '__main__': N = 5 arr = [1, -1, 2, 3, -2] replacedArray(N, arr) printArray(N, arr) N = 6 arr1 = [-3, -4, -2, 5, 1, -2] replacedArray(N, arr1) printArray(N, arr1)# This code is contributed by# Surendra_Gangwar |
C#
// C# program to implement above approachusing System;class GFG{ // Function to print the array elementsstatic void printArray(int N, int []arr){ for (int i = 0; i < N; i++) Console.Write(arr[i] + " "); Console.WriteLine();}// Function to replace all elements with // absolute difference of absolute sums // of positive and negative elementsstatic void replacedArray(int N, int []arr){ int pos_sum, neg_sum, i, j, diff; for (i = 0; i < N; i++) { pos_sum = 0; neg_sum = 0; // Calculate absolute sums of positive // and negative elements in range i+1 to N for (j = i + 1; j < N; j++) { if (arr[j] > 0) pos_sum += arr[j]; else neg_sum += arr[j]; } // calculate difference of both sums diff = Math.Abs(pos_sum) - Math.Abs(neg_sum); // replace i-th elements with absolute // difference arr[i] = Math.Abs(diff); }}// Driver codestatic void Main(){ int N = 5; int []arr = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int []arr1 = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1);}}// This code is contributed by mits |
Javascript
<script>// Javascript program to implement above approach // Function to print the array elementsfunction printArray(N, arr){ for(i = 0; i < N; i++) document.write(arr[i] + " "); document.write("<br/>");}// Function to replace all elements with// absolute difference of absolute sums// of positive and negative elementsfunction replacedArray(N, arr){ var pos_sum, neg_sum, i, j, diff; for(i = 0; i < N; i++) { pos_sum = 0; neg_sum = 0; // Calculate absolute sums of positive // and negative elements in range i+1 to N for(j = i + 1; j < N; j++) { if (arr[j] > 0) pos_sum += arr[j]; else neg_sum += arr[j]; } // Calculate difference of both sums diff = Math.abs(pos_sum) - Math.abs(neg_sum); // Replace i-th elements with absolute // difference arr[i] = Math.abs(diff); }}// Driver codevar N = 5;var arr = [ 1, -1, 2, 3, -2 ];replacedArray(N, arr);printArray(N, arr);N = 6;var arr1 = [ -3, -4, -2, 5, 1, -2 ];replacedArray(N, arr1);printArray(N, arr1);// This code is contributed by aashish1995</script> |
Output:
2 3 1 2 0 2 2 4 1 2 0
Time Complexity: O(n2), where n is the size of the given array.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Efficient Approach: Initialize positive and negative sums as 0. Now run a single for loop from the last element to the first element and calculate diff = abs(pos_sum) – abs(neg_sum).
Now if the i-th element is positive, add it to pos_sum otherwise add it to neg_sum. After all, replace the i-th element with absolute difference i.e. abs(diff).
Below is the implementation of the above approach:
C++
// C++ program to implement above approach#include <iostream>using namespace std;// Function to print the array elementsvoid printArray(int N, int arr[]){ for (int i = 0; i < N; i++) cout << arr[i] << " "; cout << endl;}// Function to replace all elements with absolute// difference of absolute sums of positive// and negative elementsvoid replacedArray(int N, int arr[]){ int pos_sum, neg_sum, i, j, diff; pos_sum = 0; neg_sum = 0; for (i = N - 1; i >= 0; i--) { // calculate difference of both sums diff = abs(pos_sum) - abs(neg_sum); // if i-th element is positive, // add it to positive sum if (arr[i] > 0) pos_sum += arr[i]; // if i-th element is negative, // add it to negative sum else neg_sum += arr[i]; // replace i-th elements with // absolute difference arr[i] = abs(diff); }}// Driver Codeint main(){ int N = 5; int arr[] = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int arr1[] = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1); return 0;} |
Java
// Java program to implement above approachclass GFG{ // Function to print the array elements static void printArray(int N, int arr[]) { for (int i = 0; i < N; i++) System.out.print(arr[i] + " "); System.out.println(); } // Function to replace all elements with absolute // difference of absolute sums of positive // and negative elements static void replacedArray(int N, int arr[]) { int pos_sum, neg_sum, i, j, diff; pos_sum = 0; neg_sum = 0; for (i = N - 1; i >= 0; i--) { // calculate difference of both sums diff = Math.abs(pos_sum) - Math.abs(neg_sum); // if i-th element is positive, // add it to positive sum if (arr[i] > 0) pos_sum += arr[i]; // if i-th element is negative, // add it to negative sum else neg_sum += arr[i]; // replace i-th elements with // absolute difference arr[i] = Math.abs(diff); } } // Driver Code public static void main (String[] args) { int N = 5; int arr[] = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int arr1[] = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1); }}// This code is contributed by ihritik |
Python3
# Python program to implement above approach# Function to print the array elementsdef printArray(N, arr) : for i in range (0, N) : print(arr[i], end=" ") print()# Function to replace all elements with absolute# difference of absolute sums of positive# and negative elementsdef replacedArray(N, arr) : pos_sum = 0 neg_sum = 0 for i in range (N - 1,-1, -1) : # calculate difference of both sums diff = abs(pos_sum) - abs(neg_sum) # if i-th element is positive, # add it to positive sum if (arr[i] > 0) : pos_sum = pos_sum + arr[i] # if i-th element is negative, # add it to negative sum else : neg_sum = neg_sum + arr[i] # replace i-th elements with # absolute difference arr[i] = abs(diff)# Driver CodeN = 5arr = [ 1, -1, 2, 3, -2 ]replacedArray(N, arr)printArray(N, arr)N = 6arr1 = [ -3, -4, -2, 5, 1, -2 ]replacedArray(N, arr1)printArray(N, arr1)# This code is contributed by ihritik |
C#
// C# program to implement above approachusing System;class GFG{ // Function to print the array elements static void printArray(int N, int [] arr) { for (int i = 0; i < N; i++) Console.Write(arr[i] + " "); Console.WriteLine(); } // Function to replace all elements with absolute // difference of absolute sums of positive // and negative elements static void replacedArray(int N, int [] arr) { int pos_sum, neg_sum, i, diff; pos_sum = 0; neg_sum = 0; for (i = N - 1; i >= 0; i--) { // calculate difference of both sums diff = Math.Abs(pos_sum) - Math.Abs(neg_sum); // if i-th element is positive, // add it to positive sum if (arr[i] > 0) pos_sum += arr[i]; // if i-th element is negative, // add it to negative sum else neg_sum += arr[i]; // replace i-th elements with // absolute difference arr[i] = Math.Abs(diff); } } // Driver Code public static void Main () { int N = 5; int [] arr = { 1, -1, 2, 3, -2 }; replacedArray(N, arr); printArray(N, arr); N = 6; int [] arr1 = { -3, -4, -2, 5, 1, -2 }; replacedArray(N, arr1); printArray(N, arr1); }}// This code is contributed by ihritik |
Javascript
<script>// Function to print the array elementsfunction printArray(N, arr){ for (var i = 0; i < N; i++) document.write( arr[i] +" "); document.write("<br>");}// Function to replace all elements with absolute// difference of absolute sums of positive// and negative elementsfunction replacedArray( N, arr){ var pos_sum, neg_sum, i, j, diff; pos_sum = 0; neg_sum = 0; for (i = N - 1; i >= 0; i--) { // calculate difference of both sums diff = Math.abs(pos_sum) - Math.abs(neg_sum); // if i-th element is positive, // add it to positive sum if (arr[i] > 0) pos_sum += arr[i]; // if i-th element is negative, // add it to negative sum else neg_sum += arr[i]; // replace i-th elements with // absolute difference arr[i] = Math.abs(diff); }}// Driver Codevar N = 5; var arr = [ 1, -1, 2, 3, -2 ]; replacedArray(N, arr); printArray(N, arr); N=6;var arr1 = [-3, -4, -2, 5, 1, -2 ]; replacedArray(N, arr1); printArray(N, arr1);</script> |
Output:
2 3 1 2 0 2 2 4 1 2 0
Time complexity: O(N), where N is the number of elements.
Auxiliary Space: O(1) as it is using constant space for variables
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
