Project Euler problem 6
Find the difference between the sum of the squares and the square of the sum of all the numbers from 1 to 100.
Solution
For such a small search space, we can iterate over all the numbers from 1 to 100 and keep a running total of the sum of the squares and the sum (which we square at the end).
#include <stdlib.h>
#include <stdio.h>
int main() {
int sum_squares = 0;
int square_sum = 0;
int difference = 0;
for (int n = 1; n <= 100; n++) {
sum_squares += n * n;
square_sum += n;
}
square_sum *= square_sum;
difference = sum_squares > square_sum ? sum_squares - square_sum : square_sum - sum_squares;
printf("%d\n", difference);
return EXIT_SUCCESS;
}
If the search space was much larger, we could optimise the sum of the numbers by pairing off the numbers and then multiplying the result. For example, the numbers 1 to 100 can be paired off as two numbers which add up to 101 (1 and 100, 2 and 99 ... 50 and 51). There are 50 such pairs, so the sum of the numbers would be: 50 x 101. This should be more efficient than simply adding up the numbers, as the loop above has:
- One add instruction for each number (100 in total).
- One comparison for each number to check whether the loop termination condition is met (n <= 100).
- One jump for each number to go back to the start of the loop.
The optimised version would have:
- One division to find the number of pairs: 100 / 2 (as this is a division by two, it can probably be optimised to a shift).
- One addition to find the value of each pair: 1 + 100.
- One multiplication to find the sum: 50 x 101.
However, on modern CPUs that can execute millions of instructions per second (especially ADD instructions, which are cheap relative to many others), it's unlikely to be a major benefit. We would also still need the loop to exist for the sum of squares.