Replace all elements by difference of sums of positive and negative numbers after that element

0 0 9 minutes read

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>

Output:

2 3 1 2 0 
2 2 4 1 2 0

Time Complexity: O(n²), 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>

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!