Can Any One Solve this Question?


  • 0
    K

    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.


  • -1
    R

    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.

    enjoy


  • 0
    K

    did not get the idea.


  • 0
    R

    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 !!


  • 0
    K

    does it mean I have to solve all equations related with any two elements in the array?


  • 0
    R

    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 !


  • 5
    M

    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.


  • 0
    K

    great idea!!
    the time and space complexity accord with the requirements.


  • 0
    F

    i believe the question does not mean those numbers range from 1 to n.


  • 0
    R

    tell me you are joking x-( :-/


  • 0
    F

    tat.. the numbers can be arbitrary, is it ? Is [ 3,3, 4,4, 9,9, 2, 5 ] a valid input?


  • 0
    K

    yes, the numbers are not in sequence. only two numbers are not duplicated.


  • 0
    R

    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.


  • 0
    F

    I am curious on how to get the expected sum and square sum efficiently, in the non-continuous case.


  • 0
    R

    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


  • 0
    F

    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.


  • 0
    R

    hmm, maybe this could be the catch. to find unique elements would take memory. thanks for pointing out.


  • 0
    F

    No problem, anyway your method is still interesting :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.