Given an array of integers of size n, every element appears 2 times except for two, which only appears once. Find out the two single ones in O(n) time, O(1) space.
its simple problem.. let x and y be missing.. sum them to get x+y and similarly sum the squares to get x2+y2 and then solve these two equations by substitution.
say you have a1,a1,a2,a2,a3,a3....ak,?,...., ay,?,an,an (here k and yth term are missing once)..
so you can get ak+ay = (expected - given array sum) (this is eq 1) - easy
and also you can get ak^2+ay^2 = (expected squares sum-given squares sum) - eq 2.
so you have 2 variables and 2 equations..solve it !!
does it mean I have to solve all equations related with any two elements in the array?
no dude...they are unknowns..you'll get only 2 solution by solving it..
take a simple eg .
1,1,2,3,3,4,5,5 (sum =24, sumofsq=90)
expected sum = 30 (which is 2*(1+...5)) and sumofsq = 110.
so x+y = 30-24=6
and x2+y2 = 134-90 = 44
hence we get quadratic eqn x2+ (6-x)^2 = 20 and if you solve this equation (i did by hand) you get x = 2 and x = 4 !! which are the missing numbers.. get your basics of maths strong !
Let x, y be the missing elements.
Let t = A1 xor A2 xor .... xor An.
It' clear that t = x xor y.
So t has at least one "1" in its bit pattern (If its bit pattern is all zero, we know that x = y, it's wrong).
Let p = index of the first "1" in bit pattern of t.
So we can split the array into 2 parts according the pth bit(Array1: pth bit = 0, Array2: pth bit = 1).
So it's clear that x and y are splited into different arrays(Because x xor y has a "1" at pth bit, so x and y are different at pth bit). BTW, the twins are always aplited into same array because they are all same. Then we xor all elements in Array1 we can get x, do the same thing with Array2 we can get y.
tat.. the numbers can be arbitrary, is it ? Is [ 3,3, 4,4, 9,9, 2, 5 ] a valid input?
if it is so, then also my method also works..its a simple solving non-linear equation style (i never used the concept of continuous series), but yes michaelalan's solution is better and my method has problem of overflow if numbers are huge.
I am curious on how to get the expected sum and square sum efficiently, in the non-continuous case.
you have to traverse it twice actually and its O(n) as is the other solution, but there might be a better solution to do that
But, does it takes O(1) space? The input may not in sorted order, I cannot think out a way by simple scanning. Please enlighten, thanks.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.