## Bloomberg LP Interview Question for Software Engineer Interns

• 0

Country: England
Interview Type: Phone Interview

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

c++, implementation, O(n)

``````int findMissingNumber(vector<int>& arr, int N) {
int i;

i = N;
while (i--) {
N ^= i ^ arr[i];
}

return N;
}``````

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

Yes it is working. Could you please explain what is happening? thanks.

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

Same number do XOR twice, result is 0.
Items are 0~N and index are 0~N.
Only missing number do XOR once.

Then result is missing number.

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

We can calculate sum of arithmetic progression (from 0 to N) and subtract actual sum of input array. Difference is the missing number.

``````int expectedSum = N * (0 + N) / 2;
int actualSum = sum(array); // trivial
return expectedSum - actualSum;``````

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

For the above solution,I think you need to use BigInt library if you want to multiply.

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

You don't have to calculate the actualSum. Just keep subtracting array elements one by one from expectedSum. This way overflow of int can be avoided

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

EDIT: A = [0,1,2,3,4,9,5,7,6]

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

``````public static int findMissingNumber(int[] arr,int n){

int result = n;

for (int i = 0 ;i<arr.length ; i++) result^=arr[i]^--n;

return result;``````

}

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

``````//Implementation in java
public class MissingNumber{
int missingNumber;
int [] arr;
int n;

for (int i = 0; i < arr.length; i = i+1){
missingNumber = result % (arr[i] = arr[i] % (n-1));
System.out.println("The missing number is" +missingNumber);

}
}``````

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

What is "n" here ?

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

``````def print_missing(l):
sumn = (1 + l[len(l)-1]) * l[len(l)-1] * (0.5)
x  = 0
for i in l:
x += i
return (sumn - x)

z = print_missing([0, 1, 2, 3, 4, 5, 7])
print(int(z))``````

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

Everyone might be answering the question but no one has actually considered the magnitude of N being really large? Any suggestion to get it to at least O(logn)?

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

It's impossible to get it to less than O(n) because we need to look at every element at least once.

If we were to ignore an element, then now you don't see 2 out of N elements, so how do you know which one is missing?

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

The question is not clear:
- Is the length of the array = N?
- [0, 1,3,4,9, 5,7,6] - 2 is also missing! What is the value of N?
- Can the numbers we repeated?

The answer will vary based on the question.

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

I find it easy enough:

``````a = [1,2,3,4,6,7,8,9]
for n in range(min(a),max(a)):
if a.count(n) == 0:
print n, 'is missing'``````

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

XOR ing a number with itself gives 0. If we XOR all the nos. from 0 to N, and also XOR the result with the elements in the array, the duplicate values are nullified, only the one missing remains-

Code -

``````public static void main(String[] args){
int[] arr = {0, 1, 3, 4, 9, 5, 7, 6, 2};
int N = 9;

System.out.println(missingnumber(arr, N));

}

public static int missingnumber(int[] arr, int N){

int res = 0;
int n = arr.length;

for(int i = 0; i <= N; i++)
res = res^i;

for(int i = 0; i < n; i++)
res = res^arr[i];

return res;

}``````

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.