Bloomberg LP Interview Question
Software Engineer InternsCountry: England
Interview Type: Phone Interview
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;
//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);
}
}
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)?
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;
}
c++, implementation, O(n)
- kyduke October 29, 2015