Find sum of all unique elements in the array for K queries
Given an arrays arr[] in which initially all elements are 0 and another array Q[][] containing K queries where every query represents a range [L, R], the task is to add 1 to each subarrays where each subarray is defined by the range [L, R], and return sum of all unique elements.
Note: One-based indexing is used in the Q[][] array to signify the ranges.
Examples:
Input: arr[] = { 0, 0, 0, 0, 0, 0 }, Q[][2] = {{1, 3}, {4, 6}, {3, 4}, {3, 3}}
Output: 6
Explanation:
Initially the array is arr[] = { 0, 0, 0, 0, 0, 0 }.
Query 1: arr[] = { 1, 1, 1, 0, 0, 0 }.
Query 2: arr[] = { 1, 1, 1, 1, 1, 1 }.
Query 3: arr[] = { 1, 1, 2, 2, 1, 1 }.
Query 4: arr[] = { 1, 1, 3, 2, 1, 1 }.
Hence unique elements are {1, 3, 2}. Thus sum = 1 + 3 + 2 = 6.
Input: arr[] = { 0, 0, 0, 0, 0, 0, 0, 0 }, Q[][2] = {{1, 4}, {5, 5}, {7, 8}, {8, 8}}
Output: 3
Explanation:
Initially the array is arr[] = { 0, 0, 0, 0, 0, 0, 0, 0 }.
After processing all queries, arr[] = { 1, 1, 1, 1, 1, 0, 1, 2 }.
Hence unique elements are {1, 0, 2}. Thus sum = 1 + 0 + 2 = 3.
Approach: The idea is to increment the value by 1 and decrement the array by 1 at L and R+1 index respectively for processing each query. Then, Compute the prefix sum of the array to find the final array after Q queries. As explained in this article. Finally, compute the sum of the unique elements with the help of the hash-map.
Below is the implementation of the above approach:
C++
// C++ implementation to find the // sum of all unique elements of // the array after Q queries #include <bits/stdc++.h> using namespace std; // Function to find the sum of // unique elements after Q Query int uniqueSum( int A[], int R[][2], int N, int M) { // Updating the array after // processing each query for ( int i = 0; i < M; ++i) { int l = R[i][0], r = R[i][1] + 1; // Making it to 0-indexing l--; r--; A[l]++; if (r < N) A[r]--; } // Iterating over the array // to get the final array for ( int i = 1; i < N; ++i) { A[i] += A[i - 1]; } // Variable to store the sum int ans = 0; // Hash to maintain previously // occurred elements unordered_set< int > s; // Loop to find the maximum sum for ( int i = 0; i < N; ++i) { if (s.find(A[i]) == s.end()) ans += A[i]; s.insert(A[i]); } return ans; } // Driver code int main() { int A[] = { 0, 0, 0, 0, 0, 0 }; int R[][2] = { { 1, 3 }, { 4, 6 }, { 3, 4 }, { 3, 3 } }; int N = sizeof (A) / sizeof (A[0]); int M = sizeof (R) / sizeof (R[0]); cout << uniqueSum(A, R, N, M); return 0; } |
Java
// Java implementation to find the // sum of all unique elements of // the array after Q queries import java.util.*; class GFG{ // Function to find the sum of // unique elements after Q Query static int uniqueSum( int A[], int R[][], int N, int M) { // Updating the array after // processing each query for ( int i = 0 ; i < M; ++i) { int l = R[i][ 0 ], r = R[i][ 1 ] + 1 ; // Making it to 0-indexing l--; r--; A[l]++; if (r < N) A[r]--; } // Iterating over the array // to get the final array for ( int i = 1 ; i < N; ++i) { A[i] += A[i - 1 ]; } // Variable to store the sum int ans = 0 ; // Hash to maintain previously // occurred elements HashSet<Integer> s = new HashSet<Integer>(); // Loop to find the maximum sum for ( int i = 0 ; i < N; ++i) { if (!s.contains(A[i])) ans += A[i]; s.add(A[i]); } return ans; } // Driver code public static void main(String[] args) { int A[] = { 0 , 0 , 0 , 0 , 0 , 0 }; int R[][] = { { 1 , 3 }, { 4 , 6 }, { 3 , 4 }, { 3 , 3 } }; int N = A.length; int M = R.length; System.out.print(uniqueSum(A, R, N, M)); } } // This code is contributed by gauravrajput1 |
Python 3
# Python implementation to find the # sum of all unique elements of # the array after Q queries # Function to find the sum of # unique elements after Q Query def uniqueSum(A, R, N, M) : # Updating the array after # processing each query for i in range ( 0 , M) : l = R[i][ 0 ] r = R[i][ 1 ] + 1 # Making it to 0-indexing l - = 1 r - = 1 A[l] + = 1 if (r < N) : A[r] - = 1 # Iterating over the array # to get the final array for i in range ( 1 , N) : A[i] + = A[i - 1 ] # Variable to store the sum ans = 0 # Hash to maintain previously # occurred elements s = { chr } # Loop to find the maximum sum for i in range ( 0 , N) : if (A[i] not in s) : ans + = A[i] s.add(A[i]) return ans # Driver code A = [ 0 , 0 , 0 , 0 , 0 , 0 ] R = [ [ 1 , 3 ], [ 4 , 6 ], [ 3 , 4 ], [ 3 , 3 ] ] N = len (A) M = len (R) print (uniqueSum(A, R, N, M)) # This code is contributed by Sanjit_Prasad |
C#
// C# implementation to find the // sum of all unique elements of // the array after Q queries using System; using System.Collections.Generic; class GFG{ // Function to find the sum of // unique elements after Q Query static int uniqueSum( int []A, int [,]R, int N, int M) { // Updating the array after // processing each query for ( int i = 0; i < M; ++i) { int l = R[i, 0], r = R[i, 1] + 1; // Making it to 0-indexing l--; r--; A[l]++; if (r < N) A[r]--; } // Iterating over the array // to get the readonly array for ( int i = 1; i < N; ++i) { A[i] += A[i - 1]; } // Variable to store the sum int ans = 0; // Hash to maintain previously // occurred elements HashSet< int > s = new HashSet< int >(); // Loop to find the maximum sum for ( int i = 0; i < N; ++i) { if (!s.Contains(A[i])) ans += A[i]; s.Add(A[i]); } return ans; } // Driver code public static void Main(String[] args) { int []A = { 0, 0, 0, 0, 0, 0 }; int [,]R = { { 1, 3 }, { 4, 6 }, { 3, 4 }, { 3, 3 } }; int N = A.Length; int M = R.GetLength(0); Console.Write(uniqueSum(A, R, N, M)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript implementation to find the // sum of all unique elements of // the array after Q queries // Function to find the sum of // unique elements after Q Query function uniqueSum(A, R, N, M) { // Updating the array after // processing each query for (let i = 0; i < M; ++i) { let l = R[i][0], r = R[i][1] + 1; // Making it to 0-indexing l--; r--; A[l]++; if (r < N) A[r]--; } // Iterating over the array // to get the final array for (let i = 1; i < N; ++i) { A[i] += A[i - 1]; } // Variable to store the sum let ans = 0; // Hash to maintain previously // occurred elements let s = new Set(); // Loop to find the maximum sum for (let i = 0; i < N; ++i) { if (!s.has(A[i])) ans += A[i]; s.add(A[i]); } return ans; } // Driver code let A = [ 0, 0, 0, 0, 0, 0 ]; let R = [[ 1, 3 ], [ 4, 6 ], [ 3, 4 ], [ 3, 3 ]]; let N = A.length; let M = R.length; document.write(uniqueSum(A, R, N, M)); // This code is contributed by code_hunt. </script> |
6
Time Complexity: O(M + N)
Auxiliary Space: O(N)