Given an array arr[] consisting of N integers, the task is to find the minimum possible sum of the array by removing all occurrences of any single array element.
Examples:
Input: N = 4, arr[] = {4, 5, 6, 6}
Output: 9
Explanation:
All distinct array elements are {4, 5, 6}.
Removing all occurrences of 4 modifies arr[] to {5, 6, 6}
Sum of the array = 17.
Removing all occurrences of 5 modifies arr[] to {4, 6, 6}
Sum of the array = 16.
Removing all occurrences of 6 modifies arr[] to {4, 5}
Sum of the array = 9.
Therefore, the minimum sum possible is 9, which is attained by deleting all occurrences of 6.Input: N = 3, arr[] = {2, 2, 2}
Output: 0
Approach: The idea to solve this problem is to first find the frequency of each element in the array and the sum of the array. Then for each unique element, find the minimum sum by finding the difference between the sum and product of the array element and its frequency.
Follow the steps below to solve the problem:
- Initialize a map, say mp, to store the frequency of array elements and a variable, say minSum, to store the minimum sum obtained after removing all occurrences of any array element.
- Traverse the array arr[] to count the frequency of each array element and store it in a Map and calculate the sum of all array elements and store it in sum.
- Traverse the map and for each key-value pair, perform the following operations:
- Subtract the product of the element and its occurrences from the sum and store the minimum sum obtained in minSum.
- Return minSum as the minimum sum obtained.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum sum after deletionint minSum(int A[], int N){ // Stores frequency of // array elements map<int, int> mp; int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Calculate sum sum += A[i]; // Update frequency of // the current element mp[A[i]]++; } // Stores the minimum // sum required int minSum = INT_MAX; // Traverse map for (auto it : mp) { // Find the minimum sum obtained minSum = min( minSum, sum - (it.first * it.second)); } // Return minimum sum return minSum;}// Driver codeint main(){ // Input array int arr[] = { 4, 5, 6, 6 }; // Size of array int N = sizeof(arr) / sizeof(arr[0]); cout << minSum(arr, N) << "\n";} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum sum after deletionstatic int minSum(int A[], int N){ // Stores frequency of // array elements HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Calculate sum sum += A[i]; // Update frequency of // the current element if(mp.containsKey(A[i])) { mp.put(A[i], mp.get(A[i]) + 1); } else { mp.put(A[i], 1); } } // Stores the minimum // sum required int minSum = Integer.MAX_VALUE; // Traverse map for (Map.Entry<Integer,Integer> it : mp.entrySet()) { // Find the minimum sum obtained minSum = Math.min( minSum, sum - (it.getKey() * it.getValue())); } // Return minimum sum return minSum;}// Driver codepublic static void main(String[] args){ // Input array int arr[] = { 4, 5, 6, 6 }; // Size of array int N = arr.length; System.out.print(minSum(arr, N)+ "\n");}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function to find minimum sum after deletiondef minSum(A, N): # Stores frequency of # array elements mp = {} sum = 0 # Traverse the array for i in range(N): # Calculate sum sum += A[i] # Update frequency of # the current element if A[i] in mp: mp[A[i]] += 1 else: mp[A[i]] = 1 # Stores the minimum # sum required minSum = float('inf') # Traverse map for it in mp: # Find the minimum sum obtained minSum = min(minSum, sum - (it * mp[it])) # Return minimum sum return minSum# Driver code# Input arrayarr = [ 4, 5, 6, 6 ]# Size of arrayN = len(arr)print(minSum(arr, N))# This code is contributed by rohitsingh07052. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find minimum sum after deletion static int minSum(int []A, int N) { // Stores frequency of // array elements Dictionary<int,int> mp = new Dictionary<int,int>(); int sum = 0; // Traverse the array for (int i = 0; i < N; i++) { // Calculate sum sum += A[i]; // Update frequency of // the current element if(mp.ContainsKey(A[i])) { mp[A[i]] = mp[A[i]] + 1; } else { mp.Add(A[i], 1); } } // Stores the minimum // sum required int minSum = int.MaxValue; // Traverse map foreach (KeyValuePair<int,int> it in mp) { // Find the minimum sum obtained minSum = Math.Min( minSum, sum - (it.Key * it.Value)); } // Return minimum sum return minSum; } // Driver code public static void Main(String[] args) { // Input array int []arr = { 4, 5, 6, 6 }; // Size of array int N = arr.Length; Console.Write(minSum(arr, N)+ "\n"); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Function to find minimum sum after deletionfunction minSum(A, N) { // Stores frequency of // array elements let mp = new Map(); let sum = 0; // Traverse the array for(let i = 0; i < N; i++) { // Calculate sum sum += A[i]; // Update frequency of // the current element mp[A[i]]++; if (mp.has(A[i])) { mp.set(A[i], mp.get(A[i]) + 1) } else { mp.set(A[i], 1) } } // Stores the minimum // sum required let minSum = Number.MAX_SAFE_INTEGER; // Traverse map for(let it of mp) { // Find the minimum sum obtained minSum = Math.min(minSum, sum - (it[0] * it[1])); } // Return minimum sum return minSum;}// Driver code// Input arraylet arr = [ 4, 5, 6, 6 ];// Size of arraylet N = arr.lengthdocument.write(minSum(arr, N) + "<br>");// This code is contributed by gfgking</script> |
Output:
9
Time Complexity: O(N)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
