1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Could you rephrase the exact question? It is not clear what the exact goal is. $\endgroup$ – Tolga Birdal Dec 14 '16 at 14:13
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just A small clarification. Is the length n or (n+1)? $\endgroup$ – Imaginary Pumpkin Dec 14 '16 at 15:04
  • 1
    $\begingroup$ If a list contains one of the numbers $1,\ldots,n$ twice and the rest once, how long is it? $\endgroup$ – Yuval Filmus Dec 14 '16 at 15:08
  • $\begingroup$ (n+1) I guess, If I understand your answer correctly $\endgroup$ – Imaginary Pumpkin Dec 14 '16 at 15:12
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "Posted to a previous question" – which previous question? You should probably provide a link. $\endgroup$ – Yuval Filmus Dec 14 '16 at 18:04
  • $\begingroup$ What do you mean, it's not fine "in computer science or in serious software development"? There are plenty of cases in both computer science and software development where you don't check the preconditions, and it's not clear that stomping the input array is worth it just to check the preconditions here. $\endgroup$ – user2357112 Dec 14 '16 at 18:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.