Forum

Post 28.04.2009   # 1
Subject 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.

public int getDivisorCount(int n) {
int count = 0;
for (int i = 1; i * i <= n; ++i) {
if (n % i == 0) {
++count;
if (n / i != i) {
++count;
}
}
}
return count;
}

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.

class Num implements Comparable<Num> {
int number;
int divisorsCount;

public Num(int number) {
this.number = number;
this.divisorsCount = getDivisorCount(number);
}

public int compareTo(Num o) {
if (this.divisorsCount != o.divisorsCount) {
return o.divisorsCount - this.divisorsCount;
} else {
return this.number - o.number;
}
}
}

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.

public int[] sort(int[] original) {

Number[] temp = new Number[original.length];
for (int i = 0; i < original.length; ++i) {
temp[i] = new Number(original[i]);
}
Arrays.sort(temp);

for (int i = 0; i < temp.length; ++i) {
original[i] = temp[i].number;
}
return original;
}
bilievsk is offline Reply

Please login to post reply.