• 1
of 1 vote

Country: India

Comment hidden because of low score. Click to expand.
2
of 2 vote

As per my understanding, the algo should be like the following
a) Sort the array in descending order of Player left
b) Keep pick 1 player each from the start and deduct it till index K-1
c) Resort (optimize by using insertion sort style starting from Index K onwards).
d) Repeat when the index K-1 reaches 0.

Comment hidden because of low score. Click to expand.
1
of 1 vote

+ Since we are required to pick each player from different country, the number of ways to pick a single player from n players is nC1 = n
+ Now it boils down to generating combinations of N countries with k size and accumulating the result of all.
+ for k = 3 and if selected countries have players {3} {2} {5}, number of teams one can build is = 3C1* 2C1* 5C1 = 3*2*5 = 30
+ generate all country combinations of size k using back and accumulate the resule using above formula.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can someone help me with this problem ?

Comment hidden because of low score. Click to expand.
0
of 0 vote

you can probably follow this greedy approach:
sort all the numbers.
try to form teams from the lowest index towards the highest index.
ex:13 11 9 3 2 2 1 and k = 3,
then, in first move
form 1 team from 2 2 1,
array is now: 13 11 9 3 1 1 0,
then form 1 team from 3 1 1,
the array now is 13 11 9 2 0 0 0.
form 2 teams from 11 9 2
the array now is 13 9 7 0 0 0 0.
form 7 teams from 13 9 7,
the array now is 6 2 0 0 0 0 0. now stop as no more teams can be formed.
total teams formed = 1 + 1 + 2 + 7 = 11

Comment hidden because of low score. Click to expand.
0

This is not the correct answer for the given example.
Start from the biggest groups: 13, 11, 9. Then, distribute
the smaller groups, so you get: 13, 11+2, 9+3+1 and
the remaining 2 players unassigned. The answer is 13
teams.

Actually, this example falls into the case where the total
number of players (41) is sufficient to create 41 / 3 = 13
teams, which is not less than the maximal group. Thus,
the players from each country can be distributed to
different teams.

Comment hidden because of low score. Click to expand.
0
of 2 vote

public class MyClass {
public static void main(String args[]) {
//call getNoOfTeams method
}

private int getNoOfTeams(Country[] countries, int teamLength) {
int result = 0;
if(countries == null || countries.length ==0 || teamLength < 1)
return result;
List<Country> list = new ArrayList<>();
PriorityQueue<Country> queue = new PriorityQueue<>(new Comparator<Country>(){
public int compare(Country c1, Country c2) {
return c2.no - c1.no;
}
});
for(Country c : countries) {
queue.offer(c);
}
while (teamLength > queue.size()) {
for(int i=0; i<teamLength; ++i) {
Country temp = queue.poll();
temp.no = temp.no-1;
if(temp.no > 0) {
}
}
++result;
for(Country item : list)
queue.offer(item);
list.clear();
}
return result;
}
}

class Country {
String name;
int no;

public Country(String name, int no) {
this.name = name;
this.no = no;
}
}

Comment hidden because of low score. Click to expand.
0

this line is while (teamLength <= queue.size()) // just a correction

Comment hidden because of low score. Click to expand.
0

Won't it get stuck in the while loop in getNoOfTeams method if teamLength is greater than queue size? Because uour teamLength remains same throughout the execution, only queue size varies. Please clear my doubt

Comment hidden because of low score. Click to expand.
0

sorry, this line is while (teamLength <= queue.size()) // just a correction

Comment hidden because of low score. Click to expand.
0
of 0 vote

check my solution at github
/dsalgoazra/dsalgorithm

it has better time complexity.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

sorry forgot to mention the class name /dsalgoazra/dsalgorithm/src/algorithm/DP/FindMaximumTeams.java

Comment hidden because of low score. Click to expand.
0

Not sure why someone would give a -ve vote for this solution. Explanation please?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I kinda did it using Kotlin, but Java should be really similar,
order the countries in descending by no of players
for K slots fill each country in one slot where the min total players is the lowest
(when the no of total players in slot clashes no of countries in the slot must be lowest)
this should give us minimum difference between the slots and the max number of teams is the min total of the slots

import java.util.*
import kotlin.collections.ArrayList

private val input = Scanner(System.`in`)

fun main(args: Array<String>) {

print("Enter no of countries N : ")
val n = input.nextInt()

val arr = ArrayList<Int>()
repeat(n) { i ->
print("Enter count of Players of Country[\${i + 1}] : ")
}
arr.sortDescending()

print("Enter size of Team K : ")
val k = input.nextInt()

val slots = ArrayList<Slots>()

arr.forEach {
slots.sortedBy { it.sArr.size }
.sortedByDescending { it.total }
.minBy { it.total }?.apply {
total += it
}
}

print("Max possible No of teams is \${slots.minBy { it.total }?.total}")

}

class Slots(var total: Int = 0, val sArr: ArrayList<Int> = ArrayList())

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Team
{
public static void main (String[] args) throws java.lang.Exception
{
int nosCountries = 5;
int nosPlayers = 5;
int teamSize = 3;
int[][] mat = new int[nosPlayers][nosCountries];
List<Integer> list = new ArrayList<>();
int[] out = {0};
int teamCount = 0;
for (int r = 0; r < mat.length; r++) {
int currTeamPlayerCount = 0;
dfs(mat, r, 0, currTeamPlayerCount, out, teamSize);
teamCount += out;
out = 0;
}
System.out.println(teamCount);
}

public static boolean isValid(int[][] mat, int p, int c) {
return p >= 0 && c >= 0 && p < mat.length && c < mat.length;
}

public static void dfs(int[][] arr, int p, int c, int currTeamPlayerCount, int[] output, int k) {
if (!isValid(arr, p, c)) {
return;
}

if (currTeamPlayerCount == k - 1) {
output++;
return;
}

for (int j = c + 1; j < arr.length; j++) {
currTeamPlayerCount++;
dfs(arr, p, j, currTeamPlayerCount, output, k);
currTeamPlayerCount--;
}

}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class GetMaxTeamsPossible {

public static int GetMaxTeams(int[] sizeOfTeams, int K)
{
if(sizeOfTeams == null || sizeOfTeams.length == 0)
{
return -1;
}

int tempK =0;
int result = 0;

PriorityQueue<Integer> visitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
PriorityQueue<Integer> unVisitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());

for(int i = 0 ;i < sizeOfTeams.length ; ++i)
{
}

while(!unVisitedTeams.isEmpty())
{

while(!unVisitedTeams.isEmpty() && tempK < K)
{
int t = unVisitedTeams.remove();
--t;
if(t > 0)
{
}

++tempK;
}

if(tempK < K)
{
break;
}

tempK=0;
++result;
visitedTeams.clear();
}

return result;
}

public static void main(String[] args)
{
int[] teamSizes = new int[] { 3, 5, 7, 3};

System.out.println("" + GetMaxTeams(teamSizes, 3));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class GetMaxTeamsPossible {

public static int GetMaxTeams(int[] sizeOfTeams, int K)
{
if(sizeOfTeams == null || sizeOfTeams.length == 0)
{
return -1;
}

int tempK =0;
int result = 0;

PriorityQueue<Integer> visitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());
PriorityQueue<Integer> unVisitedTeams = new PriorityQueue<Integer>(sizeOfTeams.length, Collections.reverseOrder());

for(int i = 0 ;i < sizeOfTeams.length ; ++i)
{
}

while(!unVisitedTeams.isEmpty())
{

while(!unVisitedTeams.isEmpty() && tempK <  K)
{
int t = unVisitedTeams.remove();
--t;
if(t > 0)
{
}

++tempK;
}

if(tempK < K)
{
break;
}

tempK=0;
++result;
visitedTeams.clear();
}

return result;
}

public static void main(String[] args)
{
int[] teamSizes = new int[] { 3, 5, 7, 3};

System.out.println("" + GetMaxTeams(teamSizes, 3));

}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a greedy algorithm approach:

1. Build a Max Heap of Country sorting by number of players, countries with most players will be picked first
2. fill priority queue with input list
3. while queue not empty: iterate collecting players from each country in each cycle until a bucket of size K is filled
4. return num of cycles executed

Implementation of the above idea in Scala:

case class Country(players: Int, name: String)

object SplitKBuckets {

def main(args: Array[String]): Unit = {

println(maxGroupsK(
List(
Country(4, "USA"),
Country(6, "CHI"),
Country(6, "IND"),
Country(3, "BRA"),
Country(2, "AUS"),
Country(1, "CAN")),
3
))

}

def sortByPlayers(c: Country) = c.players

def maxGroupsK(countries: List[Country], k: Int): Int = {
val priorityQueue: PriorityQueue[Country] = PriorityQueue()(Ordering.by(sortByPlayers))
priorityQueue ++= countries

def cycle(): Boolean = {
if (priorityQueue.isEmpty) {
false
} else {
val list = ListBuffer.empty[Country]
var count = 0

while (priorityQueue.nonEmpty && count < k) {
val c = priorityQueue.dequeue()

if (c.players > 1) {
list += Country(c.players - 1, c.name)
}
count += 1
}
priorityQueue ++= list

count == k
}
}

@tailrec def numCycles(count: Int): Int = {
if (!cycle()) count
else numCycles(count + 1)
}

numCycles(0)
}

}
/*
output: 7
*/

Comment hidden because of low score. Click to expand.
0
of 0 vote

else:
for i in range( len(L) ):
h = L[i]
nL = L[:i] + L[i+1:]
for t in pick(nL, head + [h], K):
yield t

if __name__ == '__main__':
for t in pick( ['US', 'RU', 'FL', 'CA', 'IR', 'NK', 'SK', 'UK'], [], 3):
print (t)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);

int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry = A[i];
}
i = j;
}
cout<<sum<<endl;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);

int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry = A[i];
}
i = j;
}
cout<<sum<<endl;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main() {
int N;
cin>>N;
int A[N];
for(int i=0; i<N; i++)
{
cin>>A[i];
}
int K;
cin>>K;
if(K > N)
{
return 0;
}
sort(A, A+N);

int carry = 0;
int sum = 0;
for(int i=0; i<=N-K; )
{
sum = sum + A[i] - carry;
int j = i+1;
while(j < i+ K && j < N && A[j] == A[i])
{
j++;
}
if(j == i + K)
{
carry = 0;
}
else
{
carry  = A[i];
}
i = j;
}
cout<<sum<<endl;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int countOfTeams(int* countries, int N, int K)
{
if (K == 0 || K>N) return 0;

priority_queue<int, vector<int>> maxheap;
for (int i = 0; i < N;i++)
maxheap.push(countries[i]);

vector<int> team(K);

int sum = 0;
while (K <= maxheap.size())
{
for (int i = 0; i < K; i++)
{
team[i] = maxheap.top();
maxheap.pop();
}
int count = team.back();
sum += count;

for (int i = 0; i < K; i++)
{
team[i] -= count;
if (team[i] > 0)
maxheap.push(team[i]);
}
}
return sum;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why every one choosing queue? It's not correct. This ncr problem

Comment hidden because of low score. Click to expand.
0
of 0 vote

The overall time-complexity on average is O(N(N-K)), independent of A[i].

int main( int argc, char * argv[] ){
int n,k ; cin >> n >> k;
vi v(n); input(v);
if( k > n ) return -1; // number of countries > k
if( count_if( v.begin(), v.end(), [](int x){ return x > 0; } ) < k ) return -1; // number of non-zero players countries > k.
int ans = 0;
do{
// get top K countries with maximum players
nth_element(v.begin(), v.begin()+k, v.end(), greater<int>());
ans += v[k];
// form v[k] teams, where v[k] is the smallest among top k countries.
for_each(v.begin(), v.begin()+k, [y=v[k]](int & x){ x-= y; });
}while(v[k]>0);
cout << ans << '\n';
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

An O(nlogn) solution in C++, when the team size << total number of players:

#include <iostream>

int getTeams(vector<int> &players, int teamSize)
{
if (players.empty()) return 0;

int counter = 0;

priority_queue<int> pq(players.begin(), players.end());
stack<int> tmpStack;
int n = 0;

while (pq.size() >= teamSize)
{
n = 0;
while (n < teamSize && !pq.empty())
{
tmpStack.push(pq.top() - 1);
pq.pop();

++n;
}

if (n == teamSize) ++counter;

while (!tmpStack.empty())
{
int t = tmpStack.top();
tmpStack.pop();

if (t > 0) pq.push(t);
}
}

return counter;
}

int main()
{
vector<int> v = {5, 3, 3, 5};

std::cout << getTeams(v, 3) << std::endl;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a maximum heap to store the countries, poll one country's player count each round and decrease by 1.
If there are players left, add the country back after this round (Note⚠️: not add it immediately after the poll, or it might be counted more than once in a single round).
If the size of heap is less than k, return the number of rounds.

public int maxNumberOfTeams(int[] countries, int k) {
if (countries == null || countries.length == 0 || k <= 0) return 0;
PriorityQueue<Integer> candidatePool = new PriorityQueue<>(((o1, o2) -> o2 - o1));
for (int country : countries) {
if (country <= 0) return -1;// Invalid input should be warned
candidatePool.offer(country);
}
int res = 0;
Stack<Integer> stack = new Stack<>();
while (candidatePool.size() >= k) {
for (int i = 0; i < k; i++) {
int country = candidatePool.poll();
if (--country > 0) stack.push(country);
}
while (!stack.empty()) candidatePool.offer(stack.pop());
res++;
}
return res;
}

*copied from leet code

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.