## InMobi Interview Question

• 0

Country: India
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution:
1) 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

Comment hidden because of low score. Click to expand.
0

I think its not correct.Here actually answer is "N-(sum1-sum2)".

Comment hidden because of low score. Click to expand.
0

got a little mistake... fixed it
@siva: you are doing some extra calculations, as per you

dup = N - (Sum of N numbers - Sum of array)
= N - Sum of N numbers + Sum of Array
= Sum of Array - Sum of (N-1) numbers

Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

Comment hidden because of low score. Click to expand.
0

@BugoK: you are doing some extra calculations, as per you

dup = N - (Sum of N numbers - Sum of array)
= N - Sum of N numbers + Sum of Array
= Sum of Array - Sum of (N-1) numbers

Comment hidden because of low score. Click to expand.
0
of 0 vote

keep on hashing every number before hashing any number check if it already exist . the duplicate will be found in O(n).

Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR all elements of array ^ (XOR 1 to N-1) = required number. Run time complexity is o(n) and space complexity is O(1).

Comment hidden because of low score. Click to expand.
0
of 0 vote

XOR all elements of array ^ (XOR 1 to N-1) = required number. Run time complexity is o(n) and space complexity is O(1).

Comment hidden because of low score. Click to expand.
0
of 0 vote

D = duplicate number
M = missing number
abs(D - M) = (n*(n + 1)) / 2 - (Sum of array elements)
abs(D + M) = ( (n*(n + 1)*(n + 2)) / 6 - (Sum of squares of array elements) ) / abs(D - M)

Solve the two equations.

Comment hidden because of low score. Click to expand.
0
of 0 vote

D= duplicate number
M=missing number
abs(M-D)=(n*(n + 1)) / 2 - (Sum of array elements)
abs(M+D) = ( (n*(n + 1)*(2*n+1)) / 6 - (Sum of squares of array elements) ) / abs(M-D)

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ravi Gupta's solution is good.

1. Sum of all the array elements - sum of first N-1 elements

2. Second solution: Sum up all the array elements. then XOR the result with numbers from 1 to N-1. The resultant value is the duplicate element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.