## InMobi Interview Question

**Country:**India

**Interview Type:**In-Person

Algorithm:

1. Sum up all elements in the array

2. Say that the double value is x. We know that the sum of 1, 2, ..., n is ((1+n)/2)*n. Subtract the sum we calculated is 1 from this and we get: n-x. We know n, and so we know x.

I have a different O(n) solution.

Say the array with duplicate element is called dup.

since our array has 1 to N-1 elements, declare a new array of size 'N' with all elements initialized to 0.

int a[N] with all elements initialized to 0.

for i = 0 to N

a[dup[i]]++

at the end only one position in a will have an index greater than 1 and that index will be the duplicate element

O(n) solution:

- ravigupta May 19, 20121) Find sum of first (N-1) natural numbers i.e (N(N-1))/2 : O(1) time

2) Find sum of all the elements of the array : O(n) time

Duplicate = Difference between Sum2 and Sum1