Forum
28.04.2009  # 1 
CodeFu 2009 Round 1  Problem 200
200. Divisor Sort
The main task here is to count the number of different divisors. One way to do this is to test every integer that is less then the sqrt(N) if it is a divisor of N. If so, we add two to the count of divisors. We add two because every divisor of N less than sqrt(N) must have a counterpart that is greater than sqrt(N), and when these two numbers are multiplied, the result is exactly N. If the number N is perfect square, then we count the square root as a divisor, but only once. This is the function that count the number of different divisors.
The second part of the problem is to sort the numbers. One elegant solution here is to create new class, lets say Number, which implements the Comparable interface (this way we can use the Arrays.sort() method to sort the numbers). Then, just override the compareTo() method of the class, so that it sorts the elements according to the number of divisors.
In the main method, we have to transform the int[] array in a Number[] array, sort the Numbers, and then transform back to an int[] array.


Please login to post reply.