# ACM ICPC Team: Hackerank

This is a hackerank easy question.

You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.

Note Suppose a, b, and c are three different people, then (a,b) and (b,c) are counted as two different teams.

### Input Format

The first line contains two integers, N and M, separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow. Each line contains a binary string of length M If the i'th line's j'th character is 1, then the i'th person knows the j'th topic; otherwise, he doesn't know the topic.

2≤N≤500
1≤M≤500

### Output Format

On the first line, print the maximum number of topics a 2-person team can know. On the second line, print the number of 2-person teams that can know the maximum number of topics.

Here is what I wrote:

Scanner console = new Scanner(System.in);
int n = console.nextInt();
int m = console.nextInt();
console.nextLine();
String[] arr = new String[n];
for(int p=0; p<n; p++){
String s = console.nextLine();
arr[p] = s;
}

Map<Integer, List<List<Integer>>> counts = new HashMap<>();

for(int i = 0; i< n-1; i++){

String str=arr[i];

for(int j=i+1; j<n; j++){

String secondStr = arr[j];

int count = 0;
for(int k=0; k<m; k++){

if(str.charAt(k) == '1' || secondStr.charAt(k) == '1'){
count ++;
}

}

List<Integer> mapping = new ArrayList<>();

if(counts.containsKey(count)){
List<List<Integer>> existingMappings = counts.get(count);
counts.put(count, existingMappings);
}else{
List<List<Integer>> newMappings = new ArrayList<>();
counts.put(count, newMappings);
}

}
}

int max = counts.keySet().stream().mapToInt(Integer::valueOf).max().orElse(0);

int occurences = counts.get(max).size();

System.out.println(max);
System.out.println(occurences);


This worked and passed the challenge. But it has a code smell: Too many loops and even inner loops. Any improvements?

This part can be optimized a bit, in terms of length.

List<Integer> mapping = new ArrayList<>();

if(counts.containsKey(count)){
List<List<Integer>> existingMappings = counts.get(count);
counts.put(count, existingMappings);
}else{
List<List<Integer>> newMappings = new ArrayList<>();
counts.put(count, newMappings);
}


Java 8 maps have computeIfAbsent. You can use this to "getOrCreate" the existing mapping like so:

List<Integer> mapping = new ArrayList<>();



    List<List<Integer>> existingMappings = counts.get(count);
counts.put(count, existingMappings);


There is no need to put something back into the map when you have retrieved it, because you are retrieving a pointer to a list, and you're using it to add to a list. See this Ideone that lists you put and later retrieve from the map are the same lists.

Okay, so back to this snippet.

List<Integer> mapping = new ArrayList<>();



The new ArrayList constructor can take an initialSize argument. Since you're only going to be adding two integers to the list, you could provide this information and save memory space.

List<Integer> mapping = new ArrayList<>(2);


Your algorithm could be more optimized - there's no need to count topic knowledge for a team if they know 7 topics together and there's only 6 topics left to check and the top team currently knows 14 topics. Similarily, there's no reason to store how much topics each team knows, only the teams that know the largest amount of topics, and the largest amount of topics you have currently found.

However, I think that when we look at the loops, you can't really get rid of them.

You see, there's two loops needed to make the teams (iterating people over people), and one loop needed to check the topics (iterating over topics). There are clever tricks you could use where you take the binary string and convert it to an integer, but when you do that, you're looping over the characters in the binary string - it has to read the string, after all. You just don't use a for loop.

So we're doomed to have at least 3 loops. What you CAN do is take the counting loop and put it in a separate function. That would "get rid" of one of the loops. Your static analyzer is not built with the idea of such challenges in mind - to see a method with 3 nested loops usually means the method is doing too much work.

Your solution is not optimal but you should try something better.

You can utilize BigInteger method or BitSet class to optimize andmake it easy.

For forming a team you have to use bitwise OR

Here are solutions--

   // 1st approach
static int[] acmTeam(String[] topic) {

int n = topic.length;
BigInteger[] bi = new BigInteger[n];

for (int i = 0; i < n; i++)
bi[i] = new BigInteger(topic[i], 2);

int maxTopic = 0;
int teamCount = 0;

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
BigInteger iuj = bi[i].or(bi[j]);
int bitCount = iuj.bitCount();
if (bitCount > maxTopic) {
maxTopic = bitCount;
teamCount = 1;
} else if (bitCount == maxTopic) {
teamCount++;
}
}
}

int result[] = { maxTopic, teamCount };
return result;
}

// 2nd approach--using java BitSet class
static int[] acmTeamUsingBitSet(String[] topic) {
int teamCount = 0, maxTopic = 0;
int size = topic.length;

BitSet[] bitset = new BitSet[size];
for (int i = 0; i < size; i++) {
BigInteger b1 = new BigInteger(topic[i], 2);
bitset[i] = BitSet.valueOf(b1.toByteArray());
}
for (int i = 0; i < size - 1; i++) {
BitSet bitset1 = bitset[i];
for (int j = i + 1; j < size; j++) {
BitSet bitset2 = bitset[j];
BitSet tmpset = new BitSet();
tmpset.or(bitset1);
tmpset.or(bitset2);
if (tmpset.cardinality() > maxTopic) {
maxTopic = tmpset.cardinality();
teamCount = 1;
} else if (maxTopic == tmpset.cardinality()) {
teamCount++;
}
}

}
int result[] = { maxTopic, teamCount };
return result;

}


You can refer this link for a detailed video explanation.