Given an integer array A[] and a character array B[] of equal lengths where every character of the array is from the set {‘a’, ‘b’, ‘c’}. Elements of both arrays are associated with each other i.e. the value of B[i] is linked to A[i] for all valid values of i. The task is to find the value min(a + b, c).
Examples:
Input: A[] = {3, 6, 4, 5, 6}, B[] = {‘a’, ‘c’, ‘b’, ‘b’, ‘a’}
Output: 6Input: A[] = {4, 2, 6, 2, 3}, B[] = {‘b’, ‘a’, ‘c’, ‘a’, ‘b’}
Output: 5
Approach: In order to minimize the required value, the values of a, b and c have to be minimized. So, traverse the array and find the minimum values of a, b, and c associated with these characters in the integer array and finally return min(a + b, c).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to get the minimum required valueint getMinimum(int A[], char B[], int n){ // To store the minimum values // of 'a', 'b' and 'c' int minA = INT_MAX; int minB = INT_MAX; int minC = INT_MAX; // For every value of A[] for (int i = 0; i < n; i++) { switch (B[i]) { // Update the minimum values of 'a', // 'b' and 'c' case 'a': minA = min(A[i], minA); break; case 'b': minB = min(A[i], minB); break; case 'c': minC = min(A[i], minC); break; } } // Return the minimum required value return min(minA + minB, minC);}// Driver codeint main(){ int A[] = { 4, 2, 6, 2, 3 }; char B[] = { 'b', 'a', 'c', 'a', 'b' }; int n = sizeof(A) / sizeof(A[0]); cout << getMinimum(A, B, n);} |
Java
// Java implementation of the above approachclass GFG{// Function to get the minimum required valuestatic int getMinimum(int A[], char B[], int n){ // To store the minimum values // of 'a', 'b' and 'c' int minA = Integer.MAX_VALUE; int minB = Integer.MAX_VALUE; int minC = Integer.MAX_VALUE; // For every value of A[] for (int i = 0; i < n; i++) { switch (B[i]) { // Update the minimum values of 'a', // 'b' and 'c' case 'a': minA = Math.min(A[i], minA); break; case 'b': minB = Math.min(A[i], minB); break; case 'c': minC = Math.min(A[i], minC); break; } } // Return the minimum required value return Math.min(minA + minB, minC);}// Driver codepublic static void main(String[] args) { int A[] = { 4, 2, 6, 2, 3 }; char B[] = { 'b', 'a', 'c', 'a', 'b' }; int n = A.length; System.out.println(getMinimum(A, B, n));}} // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach# Function to get the minimum required valuedef getMinimum(A, B, n): # To store the minimum values # of 'a', 'b' and 'c' minA = float('inf'); minB = float('inf'); minC = float('inf'); # For every value of A[] for i in range(n): if B[i]=='a': minA = min(A[i], minA) if B[i]=='b': minB = min(A[i], minB) if B[i]=='c': minB = min(A[i], minC) # Return the minimum required value return min(minA + minB, minC)# Driver codeif __name__ == '__main__': A = [ 4, 2, 6, 2, 3 ] B = [ 'b', 'a', 'c', 'a', 'b' ] n = len(A); print(getMinimum(A, B, n))# This code is contributed by Ashutosh450 |
C#
// C# implementation of the above approachusing System;class GFG{ // Function to get the minimum required value static int getMinimum(int []A, char []B, int n) { // To store the minimum values // of 'a', 'b' and 'c' int minA = int.MaxValue; int minB = int.MaxValue; int minC = int.MaxValue; // For every value of A[] for (int i = 0; i < n; i++) { switch (B[i]) { // Update the minimum values of 'a', // 'b' and 'c' case 'a': minA = Math.Min(A[i], minA); break; case 'b': minB = Math.Min(A[i], minB); break; case 'c': minC = Math.Min(A[i], minC); break; } } // Return the minimum required value return Math.Min(minA + minB, minC); } // Driver code public static void Main() { int []A = { 4, 2, 6, 2, 3 }; char []B = { 'b', 'a', 'c', 'a', 'b' }; int n = A.Length; Console.WriteLine(getMinimum(A, B, n)); }}// This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the approach// Function to get the minimum required valuefunction getMinimum(A, B, n){ // To store the minimum values // of 'a', 'b' and 'c' var minA = 1000000000; var minB = 1000000000; var minC = 1000000000; // For every value of A[] for (var i = 0; i < n; i++) { switch (B[i]) { // Update the minimum values of 'a', // 'b' and 'c' case 'a': minA = Math.min(A[i], minA); break; case 'b': minB = Math.min(A[i], minB); break; case 'c': minC = Math.min(A[i], minC); break; } } // Return the minimum required value return Math.min(minA + minB, minC);}// Driver codevar A = [4, 2, 6, 2, 3 ];var B = ['b', 'a', 'c', 'a', 'b'];var n = A.length;document.write( getMinimum(A, B, n));</script> |
Output:
5
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.
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!
