Find out duplicate number between 1 to N numbers 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
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.