Given an integer N denoting the numbers of cards in a specific deck and an array arr[] of size N where ith element denotes the frequency of the ith type of card. Also given K Jokers. The task is to find the maximum possible valid decks with given data.
A valid deck should follow one of the two mentioned conditions:
1. A deck containing exactly one card of each type, and no jokers.
2. A deck containing exactly one card of each type except one, and exactly one joker.
Examples:
Input: N = 2, arr[] = {10, 15}, K = 3
Output: 13
Explanation: Below are the ways in which 13 decks are made:
10 decks of type {1, 2}
3 decks of type {J, 2}
Therefore maximum possible number of decks are 10 + 3 = 13 decks.Input: N = 3, arr[] = {1, 2, 3}, K = 4
Output: 3
Explanation: Below are the ways in which 13 decks are made:
1 deck of type {1, 2, 3}
1 deck of type {J, 2, 3}
1 deck of type {J, 2, 3}
Therefore maximum possible number of decks are 1+1+1 = 3 decks.
Approach: The given problem can be solved by using Greedy Approach and Binary Search algorithm. Follow the steps below to solve the given problem.
- Sort the given array arr[] in non-decreasing order.
- binary search can be applied on the answer to get the maximum value.
- Initialize two variables say, L = 0 and R = max_element(arr) + K + 1 that will define initial range of answer to be found out.
- Iterate while L +1 < R
- Initialize a variable say mid = (L + R)/2 to keep track of the middle element in range at each iteration.
- Use a variable say, need = 0 to count the extra cards needed for the current mid element.
- iterate whole array arr[] with variable i:
- if arr[i] < mid set need = need + arr[i] – mid.
- if need <= mid and need <= k, set L = mid.
- otherwise set R = mid.
- At last final answer will be stored in L, Therefore return L as the answer.
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 maximum possible decks// with given frequency of cards and// number of jokersint maximumCardDecks(int arr[], int n, int k){ // Sort the whole array sort(arr, arr + n); // Store the binary search range int L = 0; int R = arr[n - 1] + k + 1; // Do a binary search on range while (L + 1 < R) { // Compute the mid value of the current // binary search range int mid = (L + R) / 2; // Store extra needed int need = 0; // Iterate over the total cards and // compute variable need. for (int i = 0; i < n; i++) { if (arr[i] < mid) { need += mid - arr[i]; } } if (need <= mid && need <= k) { L = mid; } else { R = mid; } } return L;}// Driver Codeint main(){ int N = 3, K = 4; int arr[] = { 1, 2, 3 }; cout << maximumCardDecks(arr, N, K);} |
Java
// Java program for the above approachimport java.io.*;import java.util.Arrays;class GFG{// Function to find maximum possible decks// with given frequency of cards and// number of jokersstatic int maximumCardDecks(int arr[], int n, int k){ // Sort the whole array Arrays.sort(arr); // Store the binary search range int L = 0; int R = arr[n - 1] + k + 1; // Do a binary search on range while (L + 1 < R) { // Compute the mid value of the current // binary search range int mid = (L + R) / 2; // Store extra needed int need = 0; // Iterate over the total cards and // compute variable need. for (int i = 0; i < n; i++) { if (arr[i] < mid) { need += mid - arr[i]; } } if (need <= mid && need <= k) { L = mid; } else { R = mid; } } return L;}// Driver Codepublic static void main (String[] args){ int N = 3, K = 4; int arr[] = { 1, 2, 3 }; System.out.print(maximumCardDecks(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Python3
# Python Program to implement# the above approach# Function to find maximum possible decks# with given frequency of cards and# number of jokersdef maximumCardDecks(arr, n, k): # Sort the whole array arr.sort() # Store the binary search range L = 0 R = arr[n - 1] + k + 1 # Do a binary search on range while (L + 1 < R) : # Compute the mid value of the current # binary search range mid = (L + R) // 2 # Store extra needed need = 0 # Iterate over the total cards and # compute variable need. for i in range(n): if (arr[i] < mid): need += mid - arr[i] if (need <= mid and need <= k): L = mid else: R = mid return L# Driver CodeN = 3K = 4arr = [1, 2, 3]print(maximumCardDecks(arr, N, K))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG{// Function to find maximum possible decks// with given frequency of cards and// number of jokersstatic int maximumCardDecks(int []arr, int n, int k){ // Sort the whole array Array.Sort(arr); // Store the binary search range int L = 0; int R = arr[n - 1] + k + 1; // Do a binary search on range while (L + 1 < R) { // Compute the mid value of the current // binary search range int mid = (L + R) / 2; // Store extra needed int need = 0; // Iterate over the total cards and // compute variable need. for (int i = 0; i < n; i++) { if (arr[i] < mid) { need += mid - arr[i]; } } if (need <= mid && need <= k) { L = mid; } else { R = mid; } } return L;}// Driver Codepublic static void Main (String[] args){ int N = 3, K = 4; int []arr = { 1, 2, 3 }; Console.Write(maximumCardDecks(arr, N, K));}}// This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find maximum possible decks // with given frequency of cards and // number of jokers function maximumCardDecks(arr, n, k) { // Sort the whole array arr.sort(function (a, b) { return a - b }) // Store the binary search range let L = 0; let R = arr[n - 1] + k + 1; // Do a binary search on range while (L + 1 < R) { // Compute the mid value of the current // binary search range let mid = (L + R) / 2; // Store extra needed let need = 0; // Iterate over the total cards and // compute variable need. for (let i = 0; i < n; i++) { if (arr[i] < mid) { need += mid - arr[i]; } } if (need <= mid && need <= k) { L = mid; } else { R = mid; } } return L; } // Driver Code let N = 3, K = 4; let arr = [1, 2, 3]; document.write(maximumCardDecks(arr, N, K));// This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N(log(N) + log(M + K)), where M is maximum element of the array.
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!
