i think XOR operator should be used to solve question.
Given the integers in the array A: n1,n2...nk,
we can do this recursively:
XOR all the integers in A, assume the result is F = n1^n2^...^nk,
F must not be 0.
for i-th bit in F from rightmost to left most:
if the i-th bit is 1, halve A into 2 parts: A1 and A2, that elements in
A1 hold 1 in the i-th bit and A2 hold 0 in the i-th bit
if XOR(A1) == 0
A1 is the result
if XOR(A2) == 0
A2 is the result
if the result has not been got, we will use the next non-zero bit in F
to halve A1 and A2
excepte the first pass,we can do some optimization so that there is no need
to compute the F with XOR one by one. we can compute F when halve the array.
but in this way , the time complexity may be not linear....
if the question is like this:
> Given an array of integers. Each number in the array repeats 3 number of
> times, but only 1 number repeated for 2 number of times. Find that number.
it can be solved in O(n), because we can use the number to eliminate some
parts.
2011/8/16 Raghavan <its...@gmail.com>
>
> - Sort the array - o(log n) based on the sorting strategy might be
> radix sort
> - check the numbers count have a counter o(1) space and again o(n) time
> - changing from one number to other check counter%2 == 0 if so then we
> get answer
>
> So consolidated time would be o(n) and space is o(1);
>
> On Tue, Aug 16, 2011 at 3:20 PM, MAC <macatad...@gmail.com> wrote:
>
>> The question needed o(1) space and o(n) time ... o(n) map approach is
>> obviously fine but space is taken up ...
>>
>>
>> On Tue, Aug 16, 2011 at 2:38 PM, Raghavan <its...@gmail.com> wrote:
>>
>>> @sukran:
>>> If you were asking for the map based solution
>>>
>>> space and time complexity would be o(n).
>>>
>>>
>>> On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan
>>> <sukrandha...@gmail.com>wrote:
>>>
>>>> what is the complexity in which it has been done ?
>>>>
>>>> On Tue, Aug 16, 2011 at 1:41 PM, MAC <macatad...@gmail.com> wrote:
>>>>
>>>>>
>>>>> Given an array of integers. Each number in the array repeats ODD number
>>>>> of times, but only 1 number repeated for EVEN number of times. Find that
>>>>> number.
>>>>>
>>>>>
>>>>> --
>>>>> thanks
>>>>> --mac
>>>>>
>>>>> --
>>>>> You received this message because you are subscribed to the Google
>>>>> Groups "Algorithm Geeks" group.
>>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>>> To unsubscribe from this group, send email to
>>>>> algogeeks+unsubscr...@googlegroups.com.
>>>>> For more options, visit this group at
>>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>>
>>>>
>>>> --
>>>> You received this message because you are subscribed to the Google
>>>> Groups "Algorithm Geeks" group.
>>>> To post to this group, send email to algogeeks@googlegroups.com.
>>>> To unsubscribe from this group, send email to
>>>> algogeeks+unsubscr...@googlegroups.com.
>>>> For more options, visit this group at
>>>> http://groups.google.com/group/algogeeks?hl=en.
>>>>
>>>
>>>
>>>
>>> --
>>> Thanks and Regards,
>>> Raghavan KL
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com.
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>
>>
>> --
>> thanks
>> --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Thanks and Regards,
> Raghavan KL
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
