HackerRank Team Formation Problem Solution

In this post, we will solve HackerRank Team Formation Problem Solution.

For an upcoming programming contest, Roy is forming some teams from the students of his university. A team can have any number of contestants.
Roy knows the skill level of each contestant. To make the teams work as a unit, he forms the teams based on some rules. Each of the team members must have a unique skill level for the team. If a member’s skill level is a[i] where 0 < . there exists another team member whose skill level is a[i] – 1. Note that a contestant can write buggy code and thus can have a negative skill level.
The more contestants on the team, the more problems they can attempt at a time so Roy wants to form teams such that the smallest team is as large as possible.
For example, there are n = 7 contestants with skill levels skills = [-1, 0, 1, 2, 2, 3]. There are many ways teams could be formed, e.g. [-1], [0]…. [3]. At the other end of the spectrum, we could form team1 = [-1, 0, 1, 2, 3] and team2 = [2]. We’re looking for the largest smaller team size though. Two sets that meet the criteria are
team1 = -1, 0, 1, 2] and team2 = [2, 3]. The largest smaller team size possible is 2.
Note: There is an edge case where 0 contestants have registered. As no teams are to be created, the largest team created will have 0 members.
Input Format
The first line contains an integer t, the number of test cases.

Output Format

For each test case, print the size of largest possible smallest team on a separate line.

Sample Input

4  
7 4 5 2 3 -4 -3 -5  
1 -4  
4 3 2 3 1  
7 1 -2 -3 -4 2 0 -1

Sample Output

Explanation

For the first case, Roy can form two teams: one with contestants with skill levels {-4,-3,-5} and the other one with {4,5,2,3}. The first group containing 3 members is the smallest.

In the second case, the only team is {-4}

In the third case, the teams are {3} , {1,2,3}, the size of the smaller group being 1.

In the last case, you can build one group containing all of the contestants. The size of the group equals the total number of contestants.

Time limits

Time limits for this challenge are given here

Note

If n = 0, print 0.

HackerRank Team Formation Problem Solution

Team Formation C Solution

#include<stdio.h>
void merge(int a[],int low,int p,int high)
{
    int n,m,i,j,k,c[100000];
    n=p-low+1;
    m=high-p;
    if(n>0 || m>0)
    {
        i=low;
        j=p+1;
        k=low;
        //printf("%d %d\n",n,m);
        while(i<=p && j<=high)
        {
            while(a[i]<=a[j] && i<=p && j<=high)
            {
                c[k++]=a[i++];
            }
            while(a[i]>=a[j] && i<=p && j<=high)
            {
                c[k++]=a[j++];
            }
        }
        if(i<=p)
        {
            while(i<=p)
            {
                c[k++]=a[i++];
            }
        }
        if(j<=high)
        {
            while(j<=high)
            {
                c[k++]=a[j++];
            }
        }
        for(i=low;i<=high;i++)
        {
            a[i]=c[i];
            //printf("%d ",a[i]);
        }
        //printf("\n");
    }
    else
    {
        return;
    }
}
void mergesort(int a[],int low,int high)
{
    int p,i;
    if(high>low)
    {
        p=(low+high)/2;
        mergesort(a,low,p);
        mergesort(a,p+1,high);
        //printf("here is the %d %d %d\n",low,p,high);
        merge(a,low,p,high);
    }
    else
    {
        return;
    }
}
int main()
{
    int a[100000],i,n,b[100010],precount,count,j,k,counter,t,t1=0,min;
    scanf("%d",&t);
    while(t1<t)
    {
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    mergesort(a,0,n-1);

    precount=0;
    count=0;
    j=-1;
    for(i=0;i<n+10;i++)
    {
        b[i]=0;
    }
    i=0;
    while(i<n-1)
    {
        if(a[i]==a[i+1])
        {
            count++;
        }
        else
        {
            count++;
            if(count<=precount)
            {
                k=j;
            }
            else // count>precount
            {
                j+=count-precount;
                k=j;
            }
            counter=0;
            while(counter<count)
            {
                b[k--]++;
                counter++;
            }
            precount=count;
            count=0;
            if(a[i]!=(a[i+1]-1))
            {
                precount=0;
            }
        }
        i++;
    }

    for(i=0;i<=j;i++)
    {
        //printf("%d %d\n",i,b[i]);
    }
    //printf("after\n");
    if(n>1)
    {
        if(a[n-2]==a[n-1])
        {
            count++;
            if(count<=precount)
            {
                k=j;
            }
            else // count>precount
            {
                j+=count-precount;
                k=j;
            }
            counter=0;
            while(counter<count)
            {
                b[k--]++;
                counter++;
            }
        }
        else if(a[n-2]==a[n-1]-1)
        {
            b[j]++;
        }
        else
        {
            b[++j]++;
        }
    }
    min=1000000000;
    for(i=0;i<=j;i++)
    {
        //printf("%d %d\n",i,b[i]);
        if(min>b[i])
        {
            min=b[i];
        }
    }
    if(n==0)
    {
        min=0;    
    }
    if(n==1)
    {
        min=1;
    }
    printf("%d\n",min);
    t1++;
    }
    return 0;
}

Team Formation C++ Solution

#include<bits/stdc++.h> 
#define ll                    long long int
#define loop(i,a,b)           for(int i=(int)a;i<(int)b;++i)
#define rloop(i,a,b)          for(int i=(int)a;i<=(int)b;++i)
#define loopl(i,a,b)          for(ll i=(ll)a;i<(ll)b;++i)
#define loopr(i,a,b)          for(int i=(int)a;i>=(int)b;--i)
#define count_1(n)            __builtin_popcountll(n)
#define pb                    push_back
#define eb                    emplace_back
#define ab(a)                 (a<0)?(-1*a):a
#define pc                    putchar_unlocked
#define gc                    getchar_unlocked
#define mset(a,b,c)           loop(i,0,b) a[i]=c
#define F                     first
#define S                     second
#define mp                    make_pair
#define clr(x)                x.clear()
#define MOD                   1000000007
#define INF                   0x3f3f3f3f
#define MAX                   1e9
#define MIN                   -1e9
#define itoc(c)               ((char)(((int)'0')+c))
#define vi                    vector<int>
#define vvi                   vector<vi>
#define vvii                  vector<vector<pair<int,int>>>
#define pll                   pair<ll,ll>
#define pii                   pair<int,int>
#define all(p)                p.begin(),p.end()
#define max(x,y)              (x>y)?x:y
#define min(x,y)              (x<y)?x:y
#define mid(s,e)              (s+(e-s)/2)
#define mini                  INT_MIN
const int MX=10010896;
const int lmt=3164;
const int N=10000001;
int flag[MX>>6];
#define ifc(i)                (flag[i>>6]&(1<<((i>>1)&31)))
#define isc(i)                (flag[i>>6]|=(1<<((i>>1)&31)))
#define chk(n)                (n==2||(n>2&&(n&1)&&!ifc(n)))
#define sv()                  int t; scanf("%d",&t); while(t--)
using namespace std;
ll extgcd(ll a,ll b,ll& x,ll& y){if(b==0){x=1;y=0;return a;}else{int g=extgcd(b,a%b,y,x);y-=a/b*x;return g;}}
ll hcf(ll a, ll b) {if(b>a) return (hcf(b, a)); if(a%b==0) return b; return (hcf(b, a%b));} 
ll modpow(ll a,ll b) {ll res=1;a%=MOD;for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
void sieve(){ int i,j,k; for(i=3;i<lmt;i+=2) if(!ifc(i)) for(j=i*i,k=i<<1;j<MX;j+=k) isc(j);}
inline void rdi(int &n) { n=0; char c=gc(); while(c<'0' or c>'9') c=gc(); while(c>='0' and c<='9') { n=(n<<3)+(n<<1)+c-'0'; c=gc();}}
inline void rdl(ll &n) { n=0; char c=gc(); while(c<'0' or c>'9') c=gc(); while(c>='0' and c<='9') { n=(n<<3)+(n<<1)+c-'0'; c=gc(); }}
inline void print(int a) { char s[20]; int i=0; do { s[i++]=a%10+'0'; a/=10; } while(a); i--; while(i>=0) pc(s[i--]); pc('\n'); }
inline void prlong(ll a) { char s[20]; int i=0; do { s[i++]=a%10+'0'; a/=10; } while(a); i--; while(i>=0) pc(s[i--]); pc('\n'); }
inline void floydWarshall(vvi& dist,int V) { loop(k,0,V){ loop(i,0,V){ loop(j,0,V){ if (dist[i][k]+ dist[k][j]<dist[i][j]) dist[i][j]=dist[i][k]+dist[k][j]; }}}}
inline void dfs(int p,vi& visit,vvi& adj){ visit[p]=true; loop(i,0,adj[p].size()){ if(visit[adj[p][i]]==false) dfs(adj[p][i],visit,adj);}}
void scanint(int &x)
{
    register int c = gc();
    x = 0;
    int neg = 0;
    for(;((c<48 || c>57) && c != '-');c = gc());
    if(c=='-') {neg=1;c=gc();}
    for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
    if(neg) x=-x;
}
 

int main() {
    sv(){
        int n,tm;
        scanint(n);
        vi num(n);
        loop(i,0,n){
            scanint(tm);
            num[i]=tm;
        }
        sort(num.begin(),num.end());
        map<int,multiset<int>> mp;
        loop(i,0,n){
            auto it=mp.find(num[i]-1);
            if(it==mp.end()){
                auto it1=mp.find(num[i]);
                if(it1==mp.end()){
                    multiset<int> ms;
                    ms.insert(1);
                    mp[num[i]]=ms;
                }
                else{
                    it1->S.insert(1);
                }
            }
            else{
                multiset<int> ms=it->S;
                auto fst=it->S.begin();
                int value=*fst;
                it->S.erase(fst);
                if(it->S.empty()){
                    mp.erase(it);
                }
                auto it1=mp.find(num[i]);
                if(it1==mp.end()){
                    multiset<int> ms;
                    ms.insert(value+1);
                    mp[num[i]]=ms;
                }
                else{
                    it1->S.insert(value+1);
                }
            }
            /*cout<<endl;
            for(auto it=mp.begin();it!=mp.end();it++){
                cout<<it->F<<" : ";
                multiset<int> ms=it->S;
                for(int i:ms){
                    cout<<i<<" ";
                }
            }
            cout<<endl;*/
        }
        int max1=1000000;
        for(auto it=mp.begin();it!=mp.end();it++){
            multiset<int> ms=it->S;
            for(int i:ms){
                if(i<max1)
                    max1=i;
            }
        }
        if(max1==1000000)
            cout<<0<<endl;
        else
            cout<<max1<<endl;
    }
    return 0;
}

Team Formation C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
  public class Team {
    public long Highest { get; set; }
    public long Size { get; set; }
    public Team (long skill) {
      Highest = skill;
      Size = 1;
    }
    public void Add(long skill) {
      Highest = skill;
      Size++;
    }
  }
    static void Main(String[] args) {
        int Q = Int32.Parse(Console.ReadLine());
        for(int q=0; q<Q; q++) {
          string[] line = Console.ReadLine().Split(new char[0]);
          long N = Int64.Parse(line[0]);
          long[] arr = new long[N];
          for(int i=1; i<=N; i++) {
            arr[i-1] = Int64.Parse(line[i]);
          }
          Array.Sort(arr);
          List<Team> teams = new List<Team>();
          for(int i=0; i<N; i++) {
            int j = teams.Count-1;
            while(j >= 0 && teams[j].Highest == arr[i]) {
              j--;
            }
            if(j == -1 || teams[j].Highest+1 != arr[i]) teams.Add(new Team(arr[i]));
            else teams[j].Add(arr[i]);
          }
          if(N == 0) Console.WriteLine("0");
          else {
            long min = teams[0].Size;
            for(int k=1; k<teams.Count; k++) {
              min = Math.Min(min, teams[k].Size);
            }
            Console.WriteLine(min);
          }
        }
    }
}

Team Formation Java Solution

// Generated by Code Flattener.
// https://plugins.jetbrains.com/plugin/9979-idea-code-flattener

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PushbackReader;
import java.io.UnsupportedEncodingException;
import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.function.Consumer;

public class TeamFormation {
    public static void main(String[] args) {
        IOUtils.iterateCases(TeamFormation::runCase);
    }

    private static void runCase(MyScanner in) {
        int n = in.nextInt();
        int[] a = in.nextIntArray(n);
        System.out.println(solveCase(n, a));
    }

    private static int solveCase(int n, int[] a) {
        if (n == 0) {
            return 0;
        }
        Arrays.sort(a);

        int[][] b = new int[n][2];
        b[0][0] = a[0];
        b[0][1] = 1;
        int m = 1;
        for (int i = 1; i < n; i++) {
            if (a[i] == b[m - 1][0]) {
                b[m - 1][1]++;
            } else {
                b[m][0] = a[i];
                b[m][1] = 1;
                m++;
            }
        }

        int pre = Integer.MIN_VALUE;
        Queue<Integer> activeTeams = new LinkedList<>();
        int shortest = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            if (b[i][0] == pre + 1) {
                while (activeTeams.size() > b[i][1]) {
                    int candidate = activeTeams.remove();
                    int length = pre - candidate + 1;
                    shortest = Math.min(shortest, length);
                }
                while (activeTeams.size() < b[i][1]) {
                    activeTeams.add(b[i][0]);
                }
            } else {
                while (!activeTeams.isEmpty()) {
                    int candidate = activeTeams.remove();
                    int length = pre - candidate + 1;
                    shortest = Math.min(shortest, length);
                }
                while (activeTeams.size() < b[i][1]) {
                    activeTeams.add(b[i][0]);
                }
            }
            pre = b[i][0];
        }
        while (!activeTeams.isEmpty()) {
            int candidate = activeTeams.remove();
            int length = pre - candidate + 1;
            shortest = Math.min(shortest, length);
        }
        return shortest;
    }

    private static class IOUtils {
        public static void iterateCases(MyScanner scanner, Consumer<MyScanner> r) {
            final int t = scanner.nextInt();
            for (int it = 0; it < t; it++) {
                r.accept(scanner);
            }
        }

        public static void iterateCases(Consumer<MyScanner> runIteration) {
            run(in -> iterateCases(in, runIteration));
        }

        public static void run(Consumer<MyScanner> block) {
            try (MyScanner in = new MyScanner();
                 MySystemOut ignored = new MySystemOut()) {
                block.accept(in);
            }
        }
    }

    private static class MyScanner implements AutoCloseable {
        private final PushbackReader br;

        public MyScanner() {
            this(System.in);
        }

        public MyScanner(InputStream in) {
            br = new PushbackReader(new BufferedReader(new InputStreamReader(in)));
        }

        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public long nextLong() {
            try {
                int read = skipNonDigits();
                boolean minus = false;
                if (read == '-') {
                    minus = true;
                    read = br.read();
                }
                long result = 0;
                while (read >= '0' && read <= '9') {
                    result = result * 10 + (read - '0');
                    read = br.read();
                }
                if (minus) {
                    return -result;
                }
                return result;

            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        private int skipNonDigits() {
            int read;
            try {
                read = br.read();
                while (read != -1 && !isDigit(read)) {
                    read = br.read();
                }
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            if (read == -1) {
                throw new RuntimeException("EOF???");
            }
            return read;
        }

        private boolean isDigit(int read) {
            return read == '-' || read >= '0' && read <= '9';
        }

        @Override
        public void close() {
            try {
                br.close();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
    }

    private static class MySystemOut implements AutoCloseable {
        private final PrintStream originalSystemOut;

        public MySystemOut() {
            originalSystemOut = System.out;
            try {
                BufferedOutputStream bufferedOutputStream = new BufferedOutputStream(System.out);
                String utf8 = StandardCharsets.UTF_8.name();
                PrintStream newPrintStream = new PrintStream(bufferedOutputStream, false, utf8);
                System.setOut(newPrintStream);
            } catch (UnsupportedEncodingException e) {
                throw new IllegalArgumentException(e);
            }
        }

        @Override
        public void close() {
            try {
                System.out.flush();
            } finally {
                System.setOut(originalSystemOut);
            }
        }
    }
}

Team Formation JavaScript Solution

let input = '';
process.stdin.on('data', data => input += data);
process.stdin.on('end', _ => {
  input = input.trim().split('\n').map(line => line.trim().split(' ').map(x => parseInt(x))).slice(1);
  for (let [_, ...arr] of input) {
    const counts = {};
    for (const x of arr) {
      if (!counts[x]) {
        counts[x] = 1;
      } else {
        counts[x]++;
      }
    }

    let min = Infinity;
    let teams = [];
    arr = [...new Set(arr)].sort((a, b) => a - b);
    let sum = 0;
    for (let i = 0; i < arr.length; i++) {
      const count = counts[arr[i]] || 0;
      if (sum <= count) {
        if (sum < count) {
          teams.push({ n: 0, count: count - sum });
        }
      } else {
        let remaining = sum - count;
        while (remaining) {
          min = Math.min(min, teams[0].n);
          if (teams[0].count > remaining) {
            teams[0].count -= remaining;
            break;
          } else {
            remaining -= teams[0].count;
            teams.shift();
          }
        }
      }
      teams.forEach(x => x.n++);
      sum = count;
      if (!counts[arr[i] + 1]) {
        min = Math.min(min, ...teams.map(x => x.n));
        teams = [];
        sum = 0;
      }
    }
    console.log(Number.isFinite(min) ? min : 0);
  }
});

/*
734 733 729 729 732 732 730 730 731
29 29 30 30 31 32 32 33 34

29 30
29 30 31 32
*/

Team Formation Python Solution

import heapq


def pop_from(dict, key):
    val = heapq.heappop(dict[key])
    if len(dict[key]) == 0:
        del dict[key]
    return val


def push_into(dict, key, value):
    if key not in dict:
        dict[key] = []
        heapq.heapify(dict[key])
    heapq.heappush(dict[key], value)


t = int(input())
for _ in range(t):
    A = list(map(int, input().split()))
    n = A[0]
    if n ==0:
        print(0)
    else:
        A = sorted(A[1:])
        teams = {}
        for i in range(n):
            if A[i] - 1 in teams:
                size = pop_from(teams, A[i] - 1)
                push_into(teams, A[i], size + 1)
            else:
                push_into(teams, A[i], 1)

        min_size = 999999
        for each in teams.values():
            min_pot = min(each)
            if min_pot < min_size:
                min_size = min_pot
        if min_size != 999999:
            print(min_size)

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python