Given two arrays A[] and B[] consisting of N integers representing the amount of each type of candies and maximum consumable limit respectively, and an integer M which represents the number of unknown candies added, the task is to find the maximum count of candies one person can consume in a blindfold.
Examples:
Input: A[] = {4, 5, 2, 3}, B[] = {8, 13, 6, 4}, M = 5
Output: 4
Explanation: Directly consume all 3 candies of 4th type and consume one more candy which can be any of type. Therefore, one can only consume total of 4 candies safely.Input: A[] = {2, 4, 1, 9, 6}, B[] = {8, 7, 3, 12, 7}, M = 0
Output: 2
Explanation: One can directly consume all candies as all types of candies are within safe limits.
Approach: The given problem can be solved based on the following observations:
- If for every type of candies, A[i] + M ? B[i], then it is safe to consume all available candies.
- Otherwise, one can only consume minimum of min(A[i] + M, B[i]) for all 0 ? i < N.
Follow the steps below to solve the problem:
- Initialize two variables, say ans and total, to store the count of maximum candies safe to consume and the total count of candies
- Initialize a variable, say allSafe = true, to check if all types of candies are safe to consume or not.
- Traverse over the range [0, N – 1] and if A[i] + M > B[i], then set allSafe = false and update ans = min(ans, B[i]). Otherwise, update ans = min(ans, A[i]).
- If allSafe is true, then print the total sum of array A[].
- Otherwise, print the result in ans.
Below is the implementation of the above approach:
C++
// C++ implementation// of the above approach#include <bits/stdc++.h>using namespace std;// Function to find the count of// maximum consumable candiesint maximumCandy(int candies[], int safety[], int N, int M){ // Store the count of total candies int total = 0; // Stores the count of maximum // consumable candies int ans = INT_MAX; // Checks if it is safe // to consume all candies bool all_safe = true; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If A[i] + M is greater than B[i] if (candies[i] + M > safety[i]) { // Mark all_safe as false all_safe = false; // Update ans ans = min(ans, safety[i]); } else { // Update ans ans = min(ans, candies[i] + M); } // Increment total by A[i] total += candies[i]; } // If all_safe is true if (all_safe) return total; // Otherwise, else return ans;}// Driver Codeint main(){ int A[] = { 2, 4, 1, 9, 6 }; int B[] = { 8, 7, 3, 12, 7 }; int M = 0; int N = sizeof(A) / sizeof(A[0]); // Function call to find // maximum consumable candies cout << maximumCandy(A, B, N, M); return 0;} |
Java
// Java implementation// of the above approachpublic class GFG{ // Function to find the count of // maximum consumable candies static int maximumCandy(int []candies, int []safety, int N, int M) { // Store the count of total candies int total = 0; // Stores the count of maximum // consumable candies int ans = Integer.MAX_VALUE; // Checks if it is safe // to consume all candies boolean all_safe = true; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If A[i] + M is greater than B[i] if (candies[i] + M > safety[i]) { // Mark all_safe as false all_safe = false; // Update ans ans = Math.min(ans, safety[i]); } else { // Update ans ans = Math.min(ans, candies[i] + M); } // Increment total by A[i] total += candies[i]; } // If all_safe is true if (all_safe) return total; // Otherwise, else return ans; } // Driver Code public static void main (String[] args) { int A[] = { 4, 5, 2, 3 }; int B[] = { 8, 13, 6, 4 }; int M = 5; int N = A.length; // Function call to find // maximum consumable candies System.out.println(maximumCandy(A, B, N, M)); }}// This code is contributed by AnkThon |
Python3
# Python3 implementation# of the above approach# Function to find the count of# maximum consumable candiesdef maximumCandy(candies, safety, N, M): # Store the count of total candies total = 0 # Stores the count of maximum # consumable candies ans = 10**8 # Checks if it is safe # to consume all candies all_safe = True # Traverse the array arr for i in range(N): # If A[i] + M is greater than B[i] if (candies[i] + M > safety[i]): # Mark all_safe as false all_safe = False # Update ans ans = min(ans, safety[i]) else: # Update ans ans = min(ans, candies[i] + M) # Increment total by A[i] total += candies[i] # If all_safe is true if (all_safe): return total # Otherwise, else: return ans# Driver Codeif __name__ == '__main__': A = [4, 5, 2, 3] B = [ 8, 13, 6, 4] M = 5 N = len(A) # Function call to find # maximum consumable candies print (maximumCandy(A, B, N, M)) # This code is contributed by mohit kumar 29. |
C#
// C# implementation// of the above approachusing System;class GFG { // Function to find the count of // maximum consumable candies static int maximumCandy(int[] candies, int[] safety, int N, int M) { // Store the count of total candies int total = 0; // Stores the count of maximum // consumable candies int ans = Int32.MaxValue; // Checks if it is safe // to consume all candies bool all_safe = true; // Traverse the array arr[] for (int i = 0; i < N; i++) { // If A[i] + M is greater than B[i] if (candies[i] + M > safety[i]) { // Mark all_safe as false all_safe = false; // Update ans ans = Math.Min(ans, safety[i]); } else { // Update ans ans = Math.Min(ans, candies[i] + M); } // Increment total by A[i] total += candies[i]; } // If all_safe is true if (all_safe) return total; // Otherwise, else return ans; } // Driver code static void Main() { int[] A = { 4, 5, 2, 3 }; int[] B = { 8, 13, 6, 4 }; int M = 5; int N = A.Length; // Function call to find // maximum consumable candies Console.WriteLine(maximumCandy(A, B, N, M)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// javascript program of the above approach // Function to find the count of // maximum consumable candies function maximumCandy(candies, safety, N, M) { // Store the count of total candies let total = 0; // Stores the count of maximum // consumable candies let ans = Number.MAX_VALUE; // Checks if it is safe // to consume all candies let all_safe = true; // Traverse the array arr[] for (let i = 0; i < N; i++) { // If A[i] + M is greater than B[i] if (candies[i] + M > safety[i]) { // Mark all_safe as false all_safe = false; // Update ans ans = Math.min(ans, safety[i]); } else { // Update ans ans = Math.min(ans, candies[i] + M); } // Increment total by A[i] total += candies[i]; } // If all_safe is true if (all_safe) return total; // Otherwise, else return ans; } // Driver Code let A = [ 4, 5, 2, 3 ]; let B = [ 8, 13, 6, 4 ]; let M = 5; let N = A.length; // Function call to find // maximum consumable candies document.write(maximumCandy(A, B, N, M));</script> |
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
