Binary watch

Solution.java

import java.util.*;
public class Solution {
  private int numberOfOneBits(int num) {
    int count = 0;
    while (num != 0) {
      if ((num & 1) == 1) {
        ++count;
      }
      num >>= 1;
    }
    return count;
  }

  public List<String> readBinaryWatch(int num) {
    List<String> results = new ArrayList<>();

    Map<Integer, List<Integer>> map = new HashMap<>();
    for (int i = 0; i < 60; ++i) {
      int bits = numberOfOneBits(i);
      if (map.containsKey(bits)) {
        map.get(bits).add(i);
      } else {
        List<Integer> possibilities = new ArrayList();
        possibilities.add(i);
        map.put(bits, possibilities);
      }
    }

    for (int i = 0; i < 4; ++i) {
      int remainingBits = num - i;
      for (int j = 0; j <= remainingBits; ++j) {
        if ((i + j) != num) { continue; }
        if (!map.containsKey(i)) { continue; }
        for (int possibilityI : map.get(i)) {
          if (!map.containsKey(j)) { continue; }
          for (int possibilityJ : map.get(j)) {
            if (possibilityI < 12 && possibilityJ < 61) {
              results.add(possibilityI + ":" + (possibilityJ < 10 ? "0" + possibilityJ : possibilityJ));
            }
          }
        }
      }
    }

    return results;
  }
}