Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 2 numbers. Find the missing numbers.
Example: Size = 5 { 1,2 3 }
Logic We can find the two numbers as follows.
Do the sum of all the numbers in the array call it sum1
Find the sum of numbers using the formulae ((n) (n+1))/2 sum2
Do the sum of squares of all the numbers in the array call it sum3
Find the sum of all squares of n numbers using the formulae (n(n+1) (2n+1))/6 = sum4
x + y = sum2 - sum1
x^2 + y^2 = sum4 - sum3
Solve these two equations You will get the answer.
Subscribe to:
Post Comments (Atom)
hey dude
ReplyDeletehere x and y are not the desired numbers.
x = missing1 - additional1
y = missing2 - additional2
so here u have 2 equestions and four variables...how will you solve???
superb answer mate
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteSo Using this method we can find any number of missing elements, Right ? (Yeah, It would be difficult to count higher powers but just wondering.)
ReplyDeletehttp://www.capacode.com/array/find-2-missing-numbers-in-array/
ReplyDeleteActually we can solve this in O(N) without solving quadratic function
If we use boolean of array to store numbers in A, then this problem is simple. It runs in O(N) and use O(N) memory. How to optimize memory here?
First, we can easily find the sum of two missing numbers which is (N * (N + 1) / 2 ) – Sum(A). For example, given the problem, sum of two missing numbers is 5. We need another information to find two missing numbers.
We can similar compute the product of two numbers which is N! / Product(A). After having sum and product of two numbers, we can easily find those numbers. However, the problem is N! can be large and overflow.
We can similar find the xor of two missing numbers. Just Xor all number in A with all numbers from 1 to N. However, Xor and Sum operator are quite similar and they can not find to which number missing.
Next is the best efficient solution as I know. We know sum of two numbers, for example, in this case is 5. Thus, one number must be less than or equal 2 and one number must be greater than or equal 3. So, next we just compute sum of all number less than or equal 2, and sum of all number greater than or equal 3. Finally we can find two missing number. Specifically, first sum is 1, second sum is 4 + 5 = 9. However, in complete array, first sum should be 1 + 2 = 3, second sum should be 3 + 4 + 5 = 12. Thus two missing number is 2 and 3 :)