Minimize Cost by selecting Distinct values from Array A
Given an array A and cost array B of size N. The task is to determine the minimum cost(given in array B) by choosing all distinct values from array A.
Note: A[i] will cost us B[i]
Examples:
Input: N = 2, A[] = {16, 16}, B[] = {1, 2}
Output: 1
Explanation: Choosing 16 at the first index will be optimal.Input: N = 3, A[] = {3, 4, 3}, B[] = {3, 2, 1}
Output: 3
Approach: To solve the problem follow the below idea:
Using map data structure, store the elements in A as key, and if we encounter less value in B for the same element, Update it.
Below are the steps involved:
- Declare a map data structure m.
- The key for the map will be valued in A and the value for the map will be cost in B.
- If we encounter the same key in array A:
- Update the corresponding value to minimum of value already existing or current cost.
- Initialize a sum variable.
- Iterate in map:
- Sum will be incremented by values of map
- Return sum.
Below is the implementation of the code:
C++
#include <bits/stdc++.h> #include <iostream> using namespace std; // Function to find minimum sum int solve( int A[], int B[], int N) { // Map declaration unordered_map< int , int > m; int i = 0; while (i < N) { if (m.find(A[i]) != m.end()) { // Update if value is present if (m[A[i]] > B[i]) { m[A[i]] = B[i]; } } else { m[A[i]] = B[i]; } i++; } int sum = 0; for ( auto a : m) { sum += a.second; } return sum; } // Driver code int main() { int N = 4; int A[] = { 3, 16, 3, 4 }; int B[] = { 3, 9, 1, 1 }; // Function call cout << solve(A, B, N); return 0; } |
Java
import java.util.HashMap; public class MinimumSum { // Function to find minimum sum static int solve( int [] A, int [] B, int N) { // Map declaration HashMap<Integer, Integer> map = new HashMap<>(); int i = 0 ; while (i < N) { if (map.containsKey(A[i])) { // Update if value is present if (map.get(A[i]) > B[i]) { map.put(A[i], B[i]); } } else { map.put(A[i], B[i]); } i++; } int sum = 0 ; // Calculating the sum of minimum values for ( int value : map.values()) { sum += value; } return sum; } // Driver code public static void main(String[] args) { int N = 4 ; int [] A = { 3 , 16 , 3 , 4 }; int [] B = { 3 , 9 , 1 , 1 }; // Function call System.out.println(solve(A, B, N)); } } |
Python3
# Function to find minimum sum def solve(A, B, N): # Dictionary declaration m = {} i = 0 while i < N: if A[i] in m: # Update if value is present if m[A[i]] > B[i]: m[A[i]] = B[i] else : m[A[i]] = B[i] i + = 1 sum_value = 0 for key, value in m.items(): sum_value + = value return sum_value # Driver code if __name__ = = "__main__" : N = 4 A = [ 3 , 16 , 3 , 4 ] B = [ 3 , 9 , 1 , 1 ] # Function call print (solve(A, B, N)) |
C#
using System; using System.Collections.Generic; public class Program { // Function to find minimum sum public static int Solve( int [] A, int [] B, int N) { // Dictionary declaration Dictionary< int , int > m = new Dictionary< int , int >(); int i = 0; while (i < N) { if (m.ContainsKey(A[i])) { // Update if value is present if (m[A[i]] > B[i]) { m[A[i]] = B[i]; } } else { m[A[i]] = B[i]; } i++; } int sum = 0; foreach ( var a in m) { sum += a.Value; } return sum; } // Driver code public static void Main( string [] args) { int N = 4; int [] A = { 3, 16, 3, 4 }; int [] B = { 3, 9, 1, 1 }; // Function call Console.WriteLine(Solve(A, B, N)); } } |
Javascript
function GFG(A, B, N) { // Create an object (dictionary) to store the minimum values for // each unique element in A const m = {}; for (let i = 0; i < N; i++) { if (m[A[i]] !== undefined) { // Update if the value is present and is greater than // the current B value if (m[A[i]] > B[i]) { m[A[i]] = B[i]; } } else { // Set the value if not present m[A[i]] = B[i]; } } // Calculate the sum of minimum values let sumValue = 0; for (const key in m) { if (m.hasOwnProperty(key)) { sumValue += m[key]; } } return sumValue; } // Driver Code const N = 4; const A = [3, 16, 3, 4]; const B = [3, 9, 1, 1]; // Function call console.log(GFG(A, B, N)); |
Output
11
Time Complexity: O(N)
Auxiliary space: O(N)