Find the sum of array after performing every query

0 0 6 minutes read

Given an array arr[] of size N and Q queries where every query contains two integers X and Y, the task is to find the sum of an array after performing each Q queries such that for every query, the element in the array arr[] with value X is updated to Y. Find the sum of the array after every query.

Examples:

Input: arr[] ={1, 2, 3, 4}, Q = {(1, 2), (3, 4), (2, 4)}
Output: 11 12 16
Explanation:
1st operation is to replace each 1 with 2
So array becomes ar[ ] ={2, 2, 3, 4} ans sum = 11
2nd operation is to replace each 3 with 4
So array becomes ar[ ] ={2, 2, 4, 4} ans sum = 12
3rd operation is to replace each 2 with 4
So array becomes ar[ ] ={4, 4, 4, 4} ans sum = 16

Input: arr[] = {1}, Q = {(1, 2)}
Output: 2

Naive Approach: The naive approach is to traverse every query and for each query update each element in the array arr[] with value X to Y by traversing the array. Print the sum of all elements in arr[] after each query is performed.
Time Complexity: O(N*Q)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach, the idea is to compute the sum of all the element in the array(say sum) arr[] and store the frequency of all elements in a unordered_map(Say M). For each query (X, Y) do the following:

Find the frequency of X from unordered_map M.
Decrease sum by X*M[X], for excluding the sum of X.
Increase sum by Y*M[X], for excluding the sum of Y.
Increase the frequency of Y in the map by M[X].
Finally, print the sum and remove X from the map M.

Below is the implementation of the above approach

C++14

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that solves the given queries
void solve(int ar[], int n, int b[],
           int c[], int q)
{
    // This map will store the
    // frequency of each element
    unordered_map<int, int> mp;
 
    // sum stores the sum of
    // all elements of array
    int sum = 0;
 
    for (int x = 0; x < n; x++) {
        sum += ar[x];
        mp[ar[x]]++;
    }
 
    // Process the queries
    for (int x = 0; x < q; x++) {
 
        // Find occurrence of
        // b[x] from map
        int occur1 = mp[b[x]];
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.erase(b[x]);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        mp] += occur1;
 
        // Print sum
        cout << sum << " ";
    }
}
 
// Driver Code
int main()
{
    // Given arr[]
    int ar[] = { 1, 2, 3, 4 };
    int n = 4;
 
    // Given Queries
    int q = 3;
    int b[] = { 1, 3, 2 };
    int c[] = { 2, 4, 4 };
 
    // Function Call
    solve(ar, n, b, c, q);
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function that solves the given queries
static void solve(int ar[], int n, int b[],
                   int c[], int q)
{
     
    // This map will store the
    // frequency of each element
    Map<Integer, Integer> mp = new HashMap<>();
 
    // sum stores the sum of
    // all elements of array
    int sum = 0;
 
    for(int x = 0; x < n; x++)
    {
        sum += ar[x];
        mp.put(ar[x], mp.getOrDefault(ar[x], 0) + 1);
    }
     
    // Process the queries
    for(int x = 0; x < q; x++) 
    {
         
        // Find occurrence of
        // b[x] from map
        int occur1 = mp.get(b[x]);
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.remove(b[x]);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        mp.put(c[x], mp.get(c[x]) + occur1);
         
        // Print sum
        System.out.print(sum + " ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given arr[]
    int ar[] = { 1, 2, 3, 4 };
    int n = 4;
     
    // Given queries
    int q = 3;
    int b[] = { 1, 3, 2 };
    int c[] = { 2, 4, 4 };
     
    // Function call
    solve(ar, n, b, c, q);
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program for the above approach
 
# Function that solves the given queries
def solve(ar, n, b, c, q):
   
    # This map will store the
    # frequency of each element
    mp = {}
     
    # sum stores the sum of
    # all elements of array
    sum = 0
 
    for x in range(n):
        sum += ar[x]
        mp[ar[x]] = mp.get(ar[x], 0) + 1
 
    # Process the queries
    for x in range(q):
       
        # Find occurrence of
        # b[x] from map
        occur1 = mp[b[x]]
 
        # Decrease sum
        sum = sum - occur1 * b[x]
 
        # Erase b[x] from map
        del mp[b[x]]
 
        # Increase sum
        sum = sum + occur1 * c[x]
 
        # Increase frequency
        # of c[x] in map
        mp] += occur1
 
        # Print sum
        print(sum, end = " ")
         
# Driver Code
if __name__ == '__main__':
   
    # Given arr[]
    ar = [ 1, 2, 3, 4 ]
    n = 4
 
    # Given Queries
    q = 3
    b = [ 1, 3, 2 ]
    c = [ 2, 4, 4 ]
 
    # Function Call
    solve(ar, n, b, c, q)
 
# This code is contributed by mohit kumar 29

C#

// C# program for 
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// Function that solves 
// the given queries
static void solve(int []ar, int n, 
                  int []b, int []c, 
                  int q)
{    
  // This map will store the
  // frequency of each element
  Dictionary<int, 
             int> mp = new Dictionary<int, 
                                      int>();
 
  // sum stores the sum of
  // all elements of array
  int sum = 0;
 
  for(int x = 0; x < n; x++)
  {
    sum += ar[x];
    if(mp.ContainsKey(ar[x]))
      mp[ar[x]] = mp[ar[x]] + 1;
    else
      mp.Add(ar[x], 1);
  }
 
  // Process the queries
  for(int x = 0; x < q; x++) 
  {
    // Find occurrence of
    // b[x] from map
    int occur1 = mp[b[x]];
 
    // Decrease sum
    sum = sum - occur1 * b[x];
 
    // Erase b[x] from map
    mp.Remove(b[x]);
 
    // Increase sum
    sum = sum + occur1 * c[x];
 
    // Increase frequency
    // of c[x] in map
    if(mp.ContainsKey(c[x]))
      mp] = mp] + occur1;
 
    // Print sum
    Console.Write(sum + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{    
  // Given []arr
  int []ar = {1, 2, 3, 4};
  int n = 4;
 
  // Given queries
  int q = 3;
  int []b = {1, 3, 2};
  int []c = {2, 4, 4};
 
  // Function call
  solve(ar, n, b, c, q);
}
}
 
// This code is contributed by Princi Singh

Javascript

<script>
 
// Javascript program for the above approach
 
// Function that solves the given queries
function solve(ar, n, b, c, q)
{
    // This map will store the
    // frequency of each element
    var mp = new Map();
 
    // sum stores the sum of
    // all elements of array
    var sum = 0;
 
    for (var x = 0; x < n; x++) {
        sum += ar[x];
        if(mp.has(ar[x]))
            mp.set(ar[x], mp.get(ar[x])+1)
        else
            mp.set(ar[x], 1);
    }
 
    // Process the queries
    for (var x = 0; x < q; x++) {
 
        // Find occurrence of
        // b[x] from map
        var occur1 = mp.get(b[x]);
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.set(b[x], 0);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        if(mp.has(c[x]))
            mp.set(c[x], mp.get(c[x])+occur1)
        else
            mp.set(c[x], occur1);
 
        // Print sum
        document.write( sum + " ");
    }
}
 
// Driver Code
// Given arr[]
var ar = [1, 2, 3, 4];
var n = 4;
// Given Queries
var q = 3;
var b = [1, 3, 2];
var c = [2, 4, 4];
// Function Call
solve(ar, n, b, c, q);
 
</script>

Output:

11 12 16

Time Complexity: O(N + Q)
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 zambiatek!