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).
package main
import "fmt"
func main() {
sumSquares := 0
squareSum := 0
difference := 0
for n := 1; n <= 100; n++ {
sumSquares += n * n
squareSum += n
}
squareSum *= squareSum
if sumSquares > squareSum {
difference = sumSquares - squareSum
} else {
difference = squareSum - sumSquares
}
fmt.Println(difference)
}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, though the compiler may choose to do something else).
- 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.