Find out duplicate number between 1 to N numbers

Question

I first saw this question on this website where I was trying on Java puzzles.

Here is the Question:-

You are given in an ArrayList, 1 to N Numbers. For Example, 1,2,3,4,5. However, one of
the numbers is repeated twice. That is, in the form 1,2,3,4,2,5. Find the duplicate number
without using loops.

I thought that this could be done with 2 For loops, and tried running the program which Worked fine. However, the question specified otherwise. Therefore, I checked the answer, which read as follows :-

int highestNumber = numbers.size() - 1;
int total = getSum(numbers);
int duplicate = total - (highestNumber*(highestNumber+1)/2);
return duplicate;

Here numbers is the List(Java) which contains the elements. The getSum(List n)method returns the sum of all the elements in the List.

Then comes this line which I fail to understand. How does total - (highestNumber*(highestNumber+1)/2); result in the correct Answer?

Edit1: As answered below the formula - n(n+1)/2 is derived from Arithmetic Progression. More details are here

Answer 1

Here is the question:

You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).

Find the number which appears twice.

The sum of numbers from $1$ to $n$ is $\frac{n(n+1)}{2}$, so if you subtract that from the sum of the list you get the number appearing twice.

Answer 2

The answer is simple, but very unsatisfying - because you don't actually know whether the claim is true or not after you give the answer. For example, if you do the calculation and the result is -3 or n+7, what now? It's fine as a puzzle, but not in computer science or in serious software development.

There is a simple O (n) algorithm, posted to a previous question, that will exchange array elements so that the elements will be ordered 1 to n, followed by the duplicate, if that is indeed what the array contained. What it actually does is storing the numbers 1 to n once into their right place, so you can then check easily which numbers are not present at all, and which one are either outside the range 1 to n, or are duplicates.