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 elements void 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 elements 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 = abs (pos_sum) - abs (neg_sum); // replace i-th elements with absolute // difference arr[i] = abs (diff); } } // Driver code int 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 approach class 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; 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 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 Akanksha Rai |
Python3
# Python 3 program to implement # above approach # Function to print the array elements def 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 elements def 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 code if __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 approach using 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, 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 code 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 mits |
Javascript
<script> // Javascript program to implement above approach // Function to print the array elements function 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 elements function 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 code var 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> |
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 elements void 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 elements 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 = 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 Code int 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 approach class 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 elements def 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 elements def 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 Code 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 ihritik |
C#
// C# program to implement above approach using 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 elements function 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 elements function 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 Code var 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> |
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
Contact Us