ACM ICPC Team: Hackerank

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

List<Integer> mapping = new ArrayList<>();
mapping.add(i+1);
mapping.add(j+1);

if(counts.containsKey(count)){
    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    counts.put(count, existingMappings);
}else{
    List<List<Integer>> newMappings = new ArrayList<>();
    newMappings.add(mapping);
    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<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

Additionally, you do this:

    List<List<Integer>> existingMappings = counts.get(count);
    existingMappings.add(mapping);
    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<>();
mapping.add(i+1);
mapping.add(j+1);

counts.computeIfAbsent(count, k -> new ArrayList<>()).add(mapping);

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.