Luís Ramalho Entrepreneur & Developer

Project Euler — Problem 31

Coin sums is a problem where one must count how many different ways a £2 coin can be made using any number of coins. Firstly, I tried to tackle this problem using brute-force, as I usually go about it. However, in this particular case and because there were so many coins (aka 8), creating a for loop for each and every coin was not a solution that I'd be happy with.

Thus, and because none of the algorithms that came to mind applied here I turned my eyes to other possible solutions in the www. In this research I found a very clever solution by Bradley, which introduced me to Integer Partition. If you are not familiar, basically:

In number theory and combinatorics, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition.

Armed with this new knowledge, I was able to easily implement the pseudo-code and obtain the right answer for the problem.

int[] coins = {1, 2, 5, 10, 20, 50, 100, 200};
return count(200, coins.length - 1, coins);
int count(int n, int m, int[] coins) {
    if (n == 0) {
        return 1;
    }
    if (n < 0) {
        return 0;
    }
    if (m < 0 && n >= 1) {
        return 0;
    }
    return count(n, m - 1, coins) + count(n - coins[m], m, coins);
}
return result;

The full solution can be found here.

Codility's CountFactors

CountFactors is a problem where one must compute the factors of a given number. Note that before attempting this problem, you should read the material on prime and composite numbers .

We incremente the count by two because based on one divisor, we can find the symmetric divisor. In other words, if a is a divisor of n then n/a is also one. The only case when that does not happen is when is if the number is in the form k^2, meaning that the symmetric divisor of k is also k.

int i = 1;
int result = 0;
while (i < Math.sqrt(n)) {
    if (n % i == 0) {
        result += 2;
    }
    i++;
}
if (Math.pow(i, 2) == n) {
    result += 1;
}
return result;

The full solution can be found here.

Codility's MaxProfit

MaxProfit is a problem where one must compute the maximum possible earnings given a log of stock prices. Note that before attempting this problem, you should read the material on maximum slice.

Our goal is to basically compute the maximum profit that ends in a given position. Thus, if we assume that the maximum profit that ends in a position i equals maxProfit then the maximum slice ending in position i + 1 is going to be max(0, maxProfit + (ai - ai - 1)).

int maxProfit = 0;
int maxSlice = 0;

for (int i = 1; i < a.length; i++) {
    maxProfit = Math.max(0, maxProfit + (a[i] - a[i - 1]));
    maxSlice = Math.max(maxSlice, maxProfit);
}

if (maxSlice < 0) {
    maxSlice = 0;
}

return maxSlice;

The full solution can be found here.