TopCoder Problem Statement - ManySquares

Determine how many squares can be made from a collection of sticks.

01: /* 02: TopCoder 03: Single Round Match: 627 04: Division: 2 05: Level: 1 06: Points: 250 07: Description: http://community.topcoder.com/stat?c=problem_statement&pm=13277 08: */ 09: 10: import java.util.HashMap; 11: import java.util.Map; 12: 13: public class ManySquares { 14: 15: public int howManySquares(int[] sticks) { 16: 17: /* 18: * Holds a mapping between the lenght of a stick, 19: * and the number of sticks found of that length. 20: */ 21: MapsticksOfLength = new HashMap<>(); 22: 23: for (int i : sticks) { 24: 25: /* 26: * If a stick of this length has already been seen, 27: * increment the count. Otherwise initialize the count for this 28: * size to 1. 29: */ 30: if (sticksOfLength.containsKey(i)) { 31: sticksOfLength.put(i, sticksOfLength.get(i) + 1); 32: } else { 33: sticksOfLength.put(i,1); 34: } 35: 36: } 37: 38: int count = 0; 39: 40: /* 41: * For each length of stick in the map, divide it's count by 4 to get 42: * the number of squares that can be made of that length. Increase 43: * the total count by that amount. 44: */ 45: for (int i : sticksOfLength.keySet()) { 46: count += sticksOfLength.get(i) / 4; // Rounds down, no fractions. 47: } 48: 49: return count; 50: } 51: }

When I began reading the problem description, I thought this was going to be a whole lot harder than it turned out to be. I envisioned having to combine sticks toghether to form each side. Maybe one 3 + 1 side, a size 4 stick on another side, and two 2 + 2 on the remaining sides. That would make an interesting problem, but it would be way beyond division 2 - 250 points.

Luckily, the problem states that the square can only be made up of 4 sticks.

I chose to use a HashMap to map a stick size, to the number of sticks found that are of that size. The Map's key is a size, and the value is the count. The for loop at line 23 iterates through the input array, and either sets or increments the count for each stick.

Then, it iterates through all the map's keys (the stick sizes), and divides the count by 4. This is integer division, so only the whole number of divisors is returned. (i.e. 3 / 4 = 0, 5 / 4 = 1). It increments the count by that amount, and finally returns the result.

## No comments:

## Post a Comment