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;
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