## Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: Phone Interview

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

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.

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

not work if 2 or more element contain same value....

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

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.

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

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.

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

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

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

even XOR will be of O(n) (time complexity).it would be batter to scan the given array,

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

Another similar way
===
Say Sum1=Sum(1..n) [ This is known frm the formula ]
Say x is missing number
Say n is replaced number >1000 [Scan the array once]
Say Sum2= Sum(Actual numbers in the array) [ This can be calculated]

Sum1-x+n = Sum2
-> x= Sum1+n-Sum2

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

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.

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

If we can go through the loop and check each number, we do not need anything else!

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

Anonymous is right. In fact, since the array's unsorted, there's not really any more efficient way to find out.

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

@Anonymous
eugene is right since the array is unsorted....just by iterating and getting "n" you can't tell which number was present there originally. So I don't think there is any more efficient way than this.

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

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)

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

what if u don't know the value of n??

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

If you don't know the number then just scan through the array once and you'll know which number is more than 1000

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

Get the number which is greater than 1000 say it is some n then to get the exact number.. n-(sum of new array - sum of old array);
this gives the exact number

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

topgun ,what a solution hats off...........

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

TopGun ,
Thanks for posting good solution

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

TopGun ,
Thanks for posting good solution

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

Say Sum1=Sum(1..n) [ This is known frm the formula ]
Say x is missing number
Say n is replaced number >1000 [Scan the array once]
Say Sum2= Sum(Actual numbers in the array) [ This can be calculated]

Sum1-x+n = Sum2
-> x= Sum1+n-Sum2

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

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;
}``````

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.