Given an array of size n. It contains numbers in the range 1 to n. Only one number is missing.Find the numbers which aren’t present.
Solution 1:
FInd the sum of all the numbers in the array
Find the sum of numbers using the formulae n(n+1)/2
Do the difference sum2 - sum1. Difference is the missing number.
Solution 2:
The problem in the above solution is that the over flow might happen since we are doing the sum of so many numbers.
Over flow can be taken care by forming a link list to store the numbers. 65535 is the maximum value of a 16 bit integer. So when the sum value reaches 65535 make a new node and append it at the starting of the list.keep the value of the sum- 65535 in new node. And keep on inserting nodes till the value is less 65,535.
Other solution could be we can xor the numbers in the array with the number 1 to n.
value = a[0]
for(int i = 1; i less than n; i++)
value = value xor array[i];
for(int i =1;il ess than n+1 ;i++)
value = value xor i;
value will have the answer finally. Since xor with same numbers will cancel out..
Subscribe to:
Post Comments (Atom)
I think your solution doesn't find missing number. OR may be I misunderstood the problem.
ReplyDeleteGiven array has n integers in range 1 to n. One number is also missing (lets say x). That means in place of x we have some other integer(lets say y) which implies one number in the given range is duplicated. When we take sum of the array and subtract it from n*(n+1)/2, all numbers except x gets nullified. We have duplicated y, so one of them remains and the result we get is equal to x-y. we still do not know what is x and y.
The second solution you have said works well. Correct me if my analysis is wrong.
Hi akshat,
ReplyDeleteCan you explain the XOR method of solving this.
I had 13423 as an example.
xor => ^
First loop:
Value = 1^3 = 2^4 = 6^2 = 4^3 = 7
Second Loop:
Value = 7^1 = 6^2 = 4^3 = 7^4 = 3^5 = 6
However, the number missing is 5.
Can you please explain; or check if this manipulation by me is correct or not.
Thanks.