@Dave : Please specify reason for choosing radix sort ?
On Thu, Sep 8, 2011 at 7:02 AM, Sandy sandy.wad...@gmail.com wrote:
Thanks Dave, Piyush, and Bittursk.
On Wed, Sep 7, 2011 at 2:48 PM, Dave dave_and_da...@juno.com wrote:
@Sandy: It can be done in O(n) time with O(n) extra space by
O(kN)
where k is the length of the numbers which are assumed to be integers, so
for even k = 100
it is O(N).
On Fri, Sep 9, 2011 at 4:27 PM, Pritpal Singh pritpal2...@gmail.com wrote:
@Dave : Please specify reason for choosing radix sort ?
On Thu, Sep 8, 2011 at 7:02 AM, Sandy
are all the numbers in a range?? say from (1 to n) and is there atleast one
occurence of each??
On Fri, Sep 9, 2011 at 5:25 PM, shady sinv...@gmail.com wrote:
O(kN)
where k is the length of the numbers which are assumed to be integers, so
for even k = 100
it is O(N).
On Fri, Sep 9, 2011
It can also be done in O(n) time and space with this. The XOR
solution of bittusrk is interesting, too. The only advantage of this
one is that it will work for any kind of object, not just numbers.
Let S be the empty set
for all elements E
if E is in S, remove it else add it
end;
for all
@Rahul - Can you explain the logic and complexity?
On Wed, Sep 7, 2011 at 11:06 PM, Rahul Thankachan rahul29ma...@gmail.comwrote:
On Sep 7, 12:43 pm, Sandy sandy.wad...@gmail.com wrote:
You have an array in which every number is repeated odd number of times
except one. Write a function
i don't think it's of O(n)
for even it's actually easy. Take the xor of all the elements you will left
with the element which appears odd number of times. O(n)
but for the odd case, we need to use extra space. Use hash map to keep the
count of each number and
take the odd one out, i mean the even
It can be done in O(n) time using a hash table as shown by the following
pseudo code:
function FindEvenRepeter(arr[])
hash_table = empty
sum = 0
for x in arr
if (x is present in hash_table)
sum = sum ^ x
else
add x to hash_table
return sum
@Sandy: It can be done in O(n) time with O(n) extra space by sorting
the data with a radix sort and then scanning the array for the element
you are seeking.
Dave
On Sep 7, 11:43 am, Sandy sandy.wad...@gmail.com wrote:
You have an array in which every number is repeated odd number of times
