From Brute Force to O(1): The Story Behind triangular number equation

Lets say you have a problem to solve. You can either try to brute force your way through it, or you can find the right approach and suddenly the problem just goes away. If someone asks me to write a program for finding n^th triangular number, the usual me would add up all the numbers from 1 to n. But when someone questions about time complexity and optimization, I search for the equation n*(n+1)/2 and the problem is solved in constant time O(1). Recently I read about a fascinationg story of how n*(n+1)/2 striked to German mathematician Carl Friedrich Gauss¹.

        fn summation (n: i32) -> i32 {
            let mut sum = 0;

            for i in 1..n+1 {
                sum += i;
            }

            sum
        }
        

        fn summation (n: i32) -> i32 {
            n * (n + 1) / 2
        }
        

One day, when Gauss was a young schoolboy, to preoccupy his students, his teacher asked them to add up all the integers from 1 to 100. Teacher expected students to take all day doing that. But young Gauss came back five minutes later with the answer, 5050. The solution is not to actually add up all the numbers, because that would be frustrating and time consuming. What he discovered was that by adding 1 and 100 you get 101. Then by adding 2 and 99 you get another 101. And by adding 3 and 98, another 101. So 50 and 51 is 101. In a matter of seconds he notices that it's 50 pairs of 101, so the answer is 5050.

Linus Torvalds in his book Just for Fun has mentioned this story as an example for thinking out of box. He points that when you look at the problem another way, you are going to have this epiphany that it was only a problem only because you were looking at it the wrong way.