Maximize card deck count that can be formed from cards of given type and joker
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 jokers int 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 Code int main() { int N = 3, K = 4; int arr[] = { 1, 2, 3 }; cout << maximumCardDecks(arr, N, K); } |
Java
// Java program for the above approach import java.io.*; import java.util.Arrays; class GFG { // Function to find maximum possible decks // with given frequency of cards and // number of jokers static 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 Code public 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 jokers def 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 Code N = 3 K = 4 arr = [ 1 , 2 , 3 ] print (maximumCardDecks(arr, N, K)) # This code is contributed by gfgking |
C#
// C# program for the above approach using System; class GFG { // Function to find maximum possible decks // with given frequency of cards and // number of jokers static 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 Code public 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> |
3
Time Complexity: O(N(log(N) + log(M + K)), where M is maximum element of the array.
Auxiliary Space: O(1)