Interview Question Software Engineer / Developers
Country: India
Interview Type: Phone Interview
I assumed that, the array contains all the 1000 nos. of which one is replaced. In case we have duplicates, there won't be a unique answer, because then the only constraint would be that the no. has to be less than or equal to 1000.
How it will work ???? The list is unsorted. x XOR n where x can be any thing from 1-1000, may be i am missing something. Please Expain.
The underlying idea is that XORing a number with itself makes it zero, i.e. a XOR a = 0
e.g. consider an array with elements from 1 to 5 in any order of which a number, say 3 (=x) is replaced with 7(=n). For simplicity let us assume that the nos. in the array are in order (it is not required).
1 2 7 4 5 -> arr[5]
1 2 3 4 5 -> Sequence from 1 to 5
XOR them all and identify n = 7 (>5)
y = 1^2^7^4^5^1^2^3^4^5
Note that, except for 3 and 7 all nos. appears twice in the XOR thus they will end up being zero. Hence the result of XOR is,
y = 7^3
Now, we can compute x as follows,
x = n ^ y
=> x = 7 ^ (7^3)
=> x = 3
1.If you know n.
Use this formula to get the missing number:
num=n-(n2-n1)
where:
sum of elements after replacing=n2
sum before replacing=n1
P.S: I am assuming all numbers are present from 1 to 1000 before replacing.
2.If n is not known:
while iterating through the array for calculating sum with replaced number just check which number is greater than thousand and that will be your n. Then follow step 1.
Anonymous is right. In fact, since the array's unsorted, there's not really any more efficient way to find out.
assuming array contains elements from 1 to 1000
1) Calculate the sum of first 1000 numbers say (sum_of_natural = (n*(n+1))/2)
2) Calculate the sum (say sum_of_array) of the array skipping the element which is > 1000 (the new element)
3) The replaced number is sum_of_natural - sum_of_array
Time Complexity O(n)
Space Complexity : O(1)
If you don't know the number then just scan through the array once and you'll know which number is more than 1000
The above algorithm can be solved using the xor concept of bit manipulation and we need to xor all the numbers from 1 to n and then we have to xor all the elements of the array as well and finally we will xor both of them together to get the element which is replaced in the array and so we will get the most optimized algorithm for the same with no extra space and time complexity of O(n).
Implementation:
int findmissing(int arr[], int n){
int array_xor = arr[0];
int number_xor = 1;
for(int i = 2; i <= n + 1; i++)
number_xor = number_xor ^ i;
for(int i = 1; i < n; i++)
array_xor = array_xor ^ arr[i];
return number_xor ^ array_xor;
}
XOR all the elements in the array and nos from 1 to 1000. Let x be the element replaced with n. After the operation we will be left with x XOR n, call it y. Since n>1000 , it can be easily determined by another scan ( or can be tracked while XOR operation). Once n is known, x equals n XOR y.
- topgun.in January 16, 2012