Handshakes
Ten people meet, and everyone shakes hands with everyone else exactly once. How many handshakes happen? What about n people?
Show hint
Each person shakes 9 hands. But if you add up 9 for each person, how many times have you counted each handshake?
Show solution
45. Ten people each shake 9 hands, which is 90, but every handshake involves two people and was counted twice: 90 / 2 = 45.
For n people it is n(n − 1) / 2. That is also the number of edges in a complete graph, and the number of pairs a nested loop like for j in range(i + 1, n) visits.
Want a problem like this every day? See today's problem and keep a streak going.