# Finding the duplicate with an array with 1,000,000 integers between 1 and 1,000,000

I recently had an interview and got to phase 2 which is a coding assessment. One of the questions was:

Given an array with 1,000,000 integers between 1 and 1,000,000, one integer is in the array twice. Find the duplicate.

I failed the interview and was wondering what improvements do I need.

/// <summary>
/// Assuming that there is no space constraint,
/// I used a HashSet to find the duplicate.
/// If the duplicate is found, assign that number as the return value
///
/// </summary>
/// <param name="givenArray">1,000,000 sized array containing ints between 1 - 1000000</param>
/// <returns>The duplicate number</returns>
public static int findDuplicate(int[] givenArray)
{
// This hashset will be filled with non duplicated numbers.
HashSet<int> nonDuplicateContainer = new HashSet<int>();
int duplicate = -1;

for (int i = 0; i < givenArray.Length; i++)
{
duplicate = givenArray[i];
break;
}
}

return duplicate;
}


Test:

/// <summary>
/// Testing with the correct duplicated number
/// </summary>
[TestMethod()]
public void FindDuplicateTestCorrectGivenDuplicate()
{
int[] testArray = InitializeOneMillionSizedArray(106500);

int testDuplicateNumber = BlueWolfSolutions.findDuplicate(testArray);

Assert.AreEqual(106500, testDuplicateNumber);
}

/// <summary>
/// Testing with the incorrect duplicated number
/// </summary>
[TestMethod()]
public void FindDuplicateTestWrongGivenDuplicate()
{
int[] testArray = InitializeOneMillionSizedArray(453234);

int testDuplicateNumber = BlueWolfSolutions.findDuplicate(testArray);

Assert.AreNotEqual(25, testDuplicateNumber);
}

• Based on your previous question about a string you should be able to solve this one with linq already ;-) Jun 30, 2016 at 20:29
• t3chb0t Yeah haha. @MartinR Oooh, that brings up a good point. I didn't think about that. Thanks for the link. This is truly helpful. Jun 30, 2016 at 20:49

There is already a good answer that describes how you could improve your tests, however, I would like to offer another solution. I had a question that was similar to this on an interview (well, I solved it using a similar method to the one I gave here).

When the interviewer asked this question, I think they wanted you to find a solution that is not only $\mathcal{O}(n)$ time but also $\mathcal{O}(1)$ space complexity. Based on the description you gave, there is one number that appears twice but there also must be one number that does not appear.

The sum of the first $n$ integers is $\frac{n(n + 1)}{2}$, and the sum of their squares is $\frac{n(n + 1) (2n + 1)}{6}$.

Let

• $sn$ = 500000500000 be the sum of all of the numbers from 1 to 1000000
• $sn2$ = 333333833333500000 be the sum of their squares
• $sn'$ be the sum of the elements of the array
• $sn2'$ be the sum of their squares

Then there are numbers $d$ (double) and $m$ (missing) such that

$$sn' + m - d = sn$$ $$sn2' + m^2 - d^2 = sn2$$

Solving the first equation for $m$ and substituting into the second, we get

$$sn2' + (sn + d - sn')^2 - d^2 = sn2$$

Expand and collect like terms

$$sn2' + (sn - sn')^2 + 2 (sn - sn')d = sn2$$

Thus

$$d = \dfrac{(sn2 - sn2') - (sn - sn')^2}{2 (sn - sn')}$$

Here is a version of findDuplicate that uses this rule (note that I have never used C# so there may be a couple of mistakes, and I did not put in comments since you've already read the explanation of how I got the formula):

/// <summary>
/// Find the duplicate number in a length n array where all elements are numbers
/// from 1 to n, all appearing once except for one duplicate (and consequently one
/// missing).
///
/// </summary>
/// <param name="givenArray">n sized array containing ints between 1 - n inclusive</param>
/// <returns>The duplicate number</returns>
public static int findDuplicate(int[] givenArray)
{
ulong n = givenArray.Length, dsn, dsn2;
dsn = n*(n + 1)/2;
dsn2 = dsn*(2*n + 1)/3;
for(ulong i = 0; i < n; ++i){
dsn -= givenArray[i];
dsn2 -= givenArray[i]*givenArray[i];
}
return (dsn2 - dsn*dsn)/(2*dsn);
}


Note that this method of finding extra or missing numbers in a list that is otherwise a range can be extended simply by adding equations for higher powers (cubes and beyond).

• math always beats everything ;-) Jul 1, 2016 at 6:02

Test Cases

The FindDuplicateTestWrongGivenDuplicate test really odd. You've basically saying, make sure that when I put 453234 into the array twice, my code doesn't tell me that the duplicate is 25. This might make some sense if your other test used the value 25, but it doesn't so 25 just comes from nowhere.

You haven't posted the code for InitializeOneMillionSizedArray, however I did look at it in your gist and it's creating an array, then putting the duplicate in a random position within the array. Generally speaking, try to avoid random in your tests because it can result in non-deterministic tests (tests that fail sometimes and pass other times with no changes to code).

Some better edge case tests might be:

• CheckDuplicateFoundWhenPlacedAtStartOfArray
• CheckDuplicateFoundWhenPlacedAtEndOfArray
• CheckDuplicateFoundWhenAfterDuplicateValue
• CheckDuplicateFoundWhenSeperatedFromDuplicateValue
• CheckDuplicateFoundWhenDuplicateIsZero
• CheckDuplicateFoundWhenDuplicateIsNegative
• CheckDuplicateFoundWhenDuplicateIsPositive

All of which would test that the expected value is returned. You might also consider adding negative tests, although they're not covered by your requirements to demonstrate you thought about them and what to do in those situations:

• TestFirstDuplicateReturnedWhenMultipleDuplicatesExist
• TestInvalidArgumentThrownWhenNoDuplicatesExist

Other stuff

The variable duplicate isn't really needed, you could simply return when found:

if (!nonDuplicateContainer.Add(givenArray[i])) {
return givenArray[i];
}


This would make it easier to handle errors (by throwing?) if you make it out of the for loop without finding a duplicate. At the moment, you'll return -1 which could be misleading, since you're using ints, not unsigneds in your array and -1 is a valid answer.

• I forgot to post the code for that function, sorry for the inconvenience. The feedback is very helpful and those are some good test cases. Question though, how do we usually determine edge cases? I'm having a hard time trying to determine those edge cases for testing. Is there any guidelines? Also for the "Other stuff" I learned that giving a variable will give other coders to understand it better. On the other hand, your reasoning is correct. Jun 30, 2016 at 21:51

One possible improvement could be to implement more concisely using LINQ:

public static int? FindDuplicate(int[] givenArray) =>
givenArray.GroupBy(x => x)
.FirstOrDefault(x => x.Count() > 1)?.Key;


This is significantly shorter, elegant, and reads like a sentence.

Demonstrating working knowledge of LINQ could have been a good point in your favor, and definitely worth building up for the future.

• This is using O(n) space. Code-wise it might be an improvement as it allows you to write it more compactly, but performance-wise it is not an improvement. Also please avoid giving answers that are essentially saying "This is what I would do" without arguing for why it is a better way of doing it. Jul 1, 2016 at 14:08
• Your comment is completely pointless, the question doesn't put any memory/time constraint and the fact that it's much more concise speak for itself. Jul 1, 2016 at 17:52
• As a rule, since this is Code Review, you must say something about the code in the question. If you opt to rewrite it, and the rewrite is not completely superior in every conceivable way, you should add your reasoning. Jul 1, 2016 at 19:21
• This is Code Review. A good answer reviews the posted code, and provides guidance to the OP how to do better next time. This answer has serious issues with wording. Phrases like "just for fun" and "haven't tested performances" give the impression that you don't care. The downvotes are not surprising. I adjusted your text now. Downvotes are trying to urge you to improve the answer, and once that's done, they often go away. Jul 2, 2016 at 12:53
• @janos thank you. This is a constructive comment. I do agree it was a bit rushed. I wrote "just for fun" as the answer was already chosen, therefore I just presented a brief alternative without putting much effort. I still think is a valid answer and fit for the question. Next time I'll present it in a cleaner fashion. Jul 2, 2016 at 15:17

I have solved it using similar thinking as @hacatu, but slightly different. I find this more intuitive, but it is just my opinion. If it helps someone, great. If someone thinks it is worst then @hacatu solution, please explain why. (I should say that variables in this solution hold smaller values than in @hacatu's)

As @hacatu said, there must be one value that is missing (m), and one value that is duplicate (d).

If you sum differences between indexes and values: you will get something like:

0 - array[0] + 1 - array[1] + 2 - array[2] + ....


Since array all values (except duplicate value) have matching index with same value, all will cancel out and only difference diff = m - d will remain. Similarly we can find diffsq = m^2 - d^2.

This pseudo code saves difference m - d into variable diff, and m^2 - d^2 to diffsq.

diff = 0;
diffsq = 0;
for (; i < array.length; ++i) {
diff += i - array[i];
diffsq += i*i - array[i]*array[i];
}


Now diffsq = m^2 - d^2 = (m - d)*(m + d) = diff * (m + d). Which gives us two equations:

m + d = diffsq/diff

m - d = diff

Solving them for d gives:

d = (diffsq/diff - diff) / 2

Here is C code, which assumes that there is exactly one duplicate in array that would otherwise be unsorted range.

(I should also say that I'm not competing with @hacatu, I want to give more options, and hopefully learn something form comments.)

EDIT: Now I see that my solution is for number in range [0, n-1], and not [1, n]. I have found this question as I was looking for different answers, but my problem was slightly differently formulated.