SolsmaDev - 1 year ago 52

Java Question

I'm having a great deal of trouble trying to figure this question out, and the root of that trouble is creating an algorithm of

`O(n)`

An Arrayof length`A`

contains integers from the range`n`

. However, it only contains`[0, .., n - 1]`

distinct numbers. So one of the numbers is missing and another number is duplicated. Write a Java method that takes`n - 1`

as an input argument and returns the missing number; the method should run in`A`

.`O(n)`

For example, when,`A = [0, 2, 1, 2, 4]`

should return`oddOneOut()`

; when`3`

,`A = [3, 0, 0, 4, 2, 1]`

should return`oddOneOut()`

.`5`

Obviously this is an easy problem to solve with an

`O(n`^{2})

`O(n)`

Thank you in advance...

Answer Source

Suppose the number missing is `x`

and the duplicate is `y`

. If you add all numbers, the sum will be:

```
(n - 1) * n / 2 - x + y
```

From the above, you can find `(x - y)`

.....(1)

Similarly, sum the squares of the numbers. The sum will then be:

`(n - 1) * n * (2 * n - 1) / 6 - x`

^{2}+ y^{2}

From the above you get `(x`

....(2)^{2} - y^{2})

```
(2) / (1) gives (x + y).....(3)
```

(1) + (3) gives `2 * x`

and you can thereby find `x`

and `y`

.

Note that in this solution there is ** O(1) extra storage** and is

`O(n)`

time complexity`O(n)`

extra storage.Code in mixed C/C++ for some more clarity:

```
#include <stdio.h>
int findDup(int *arr, int n, int& dup, int& missing)
{
int sum = 0;
int squares = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
squares += arr[i] * arr[i];
}
sum = (n - 1) * n / 2 - sum; // x - y
squares = (n - 1) * n * (2 * (n - 1) + 1) / 6 - squares; // x^2 - y^2
if (sum == 0) {
// no duplicates
missing = dup = 0;
return -1;
}
missing = (squares / sum + sum) / 2; // ((x^2 - y^2) / (x - y) + (x - y)) / 2 = ((x + y) + (x - y)) / 2 = x
dup = missing - sum; // x - (x - y) = y
return 0;
}
int main(int argc, char *argv[])
{
int dup = 0;
int missing = 0;
int a[] = {0, 2, 1, 2, 4};
findDup(a, sizeof(a) / sizeof(int), dup, missing);
printf("dup = [%d], missing = [%d]\n", dup, missing);
int b[] = {3, 0, 0, 4, 2, 1};
findDup(b, sizeof(b) / sizeof(int), dup, missing);
printf("dup = [%d], missing = [%d]\n", dup, missing);
return 0;
}
```

Output:

```
dup = [2], missing = [3]
dup = [0], missing = [5]
```