[algogeeks] Re: Finding repeated element in most efficient way

I think your solution will work if the repeated number is a power of 2. The problem states that the repeated number is repeated 2, 4, 8, 16 times. for ex: consider 3,4,3 3 is repeated two times. your algo will return i when i=4 So i feel this is not the correct solution Rega

[algogeeks] Re: Finding repeated element in most efficient way

each number except one is there only once, and one number that repeats can repeat power of two times. 2,4,8,16. the best solution is to use trie, it is linear in number of bits of input. But It is interresting if there is solution using unit cost arithmetics. Or by using randomized algorithm, and

[algogeeks] Re: Finding repeated element in most efficient way

if value in array is in something like millions.. then bit variable shud be having millions bits rite ??? means bits variable = pow(2,millions) rite... ?? result:- not possible.. for n=4 1,1,2,2 then think .. ?? On Mon, Aug 17, 2009 at 5:32 AM, Shyam wrote: > >

[algogeeks] Re: Finding repeated element in most efficient way

Any Body can tell me what is the exact problem? because i m reading this thread 1st time over here. whether u wanna one repeated element in array or all set of all repeated element in given array. i have some solution with single traversal without using extra space but they depend on constraint so

[algogeeks] Re: Finding repeated element in most efficient way

I think I could do it in O(n) . var bits=0 var @array for each i in array if (bits & i)!=0 return i else bits=bits | i; end if end for I just use the pattern for powers of two let array be 2,4,2 so first bits=0 i=2 so bits(000) & i(010) is 0 so bits= bits |

[algogeeks] Re: Finding repeated element in most efficient way

gogeeks@googlegroups.com > > Sent: Sunday, 9 August, 2009 5:47:32 PM > > Subject: [algogeeks] Re: Finding repeated element in most efficient way > > > @richa.. > > ques is in complete i think . > > there shud be some conditions given .. > > > otherwise >

[algogeeks] Re: Finding repeated element in most efficient way

oups.com > Sent: Sunday, 9 August, 2009 5:47:32 PM > Subject: [algogeeks] Re: Finding repeated element in most efficient way > > @richa.. > ques is in complete i think . > there shud be some conditions given .. > > otherwise > hash them > but lots of space will b was

[algogeeks] Re: Finding repeated element in most efficient way

the repeated number. >>> But the catch is that number is repeated 2^i times. That is the hint we >>> should use >>> >>> ---------- >>> *From:* ankur aggarwal >>> *To:* algogeeks@googlegroups.com >>> *Sent:* Sunday, 9 August,

[algogeeks] Re: Finding repeated element in most efficient way

eeks@googlegroups.com >> *Sent:* Sunday, 9 August, 2009 5:47:32 PM >> *Subject:* [algogeeks] Re: Finding repeated element in most efficient way >> >> >> @richa.. >> ques is in complete i think . >> there shud be some conditions given ..

[algogeeks] Re: Finding repeated element in most efficient way

>> *To:* algogeeks@googlegroups.com >> *Sent:* Sunday, 9 August, 2009 5:47:32 PM >> *Subject:* [algogeeks] Re: Finding repeated element in most efficient way >> >> >> @richa.. >> ques is in complete i think . >> there shud be some conditions given ..

[algogeeks] Re: Finding repeated element in most efficient way

; should use > > -- > *From:* ankur aggarwal > *To:* algogeeks@googlegroups.com > *Sent:* Sunday, 9 August, 2009 5:47:32 PM > *Subject:* [algogeeks] Re: Finding repeated element in most efficient way > > > @richa.. > ques is in complete i thi

[algogeeks] Re: Finding repeated element in most efficient way

: algogeeks@googlegroups.com Sent: Sunday, 9 August, 2009 5:47:32 PM Subject: [algogeeks] Re: Finding repeated element in most efficient way @richa.. ques is in complete i think . there shud be some conditions given .. otherwise hash them but lots of space will b wasted.. or sort them try to

[algogeeks] Re: Finding repeated element in most efficient way

@ Anshya Aggarwal how xoring will help plz explain .. --~--~-~--~~~---~--~~ 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

[algogeeks] Re: Finding repeated element in most efficient way

xoring will work On Sun, Aug 9, 2009 at 5:59 PM, Vikram Sridar wrote: > Sorting will tkae atleast a nlog(n)... this could be done in 0(n) if we > hash.. worst case that is > > > > > -- Anshya Aggarwal Sent from Delhi, DL, India --~--~-~--~~~---~--~~ You receive

[algogeeks] Re: Finding repeated element in most efficient way

sorry, i thought the element that is repeated is of the form 2^i. :D On Sun, Aug 9, 2009 at 6:14 PM, Siddharth S wrote: > assuming the numbers are n-bit numbers, > 1. have an array, "arr", of n elements, initialize all elements with 0. > 2. traverse the "input" array > 3. if input[i] is a power

[algogeeks] Re: Finding repeated element in most efficient way

assuming the numbers are n-bit numbers, 1. have an array, "arr", of n elements, initialize all elements with 0. 2. traverse the "input" array 3. if input[i] is a power of 2, arr[ lg(input[i]) ] ++; // where lg is logarithm to the base 2. 4. after traversing input array, see if any element i

[algogeeks] Re: Finding repeated element in most efficient way

Sorting will tkae atleast a nlog(n)... this could be done in 0(n) if we hash.. worst case that is --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks

[algogeeks] Re: Finding repeated element in most efficient way

@richa.. ques is in complete i think . there shud be some conditions given .. otherwise hash them but lots of space will b wasted.. or sort them try to put the conditions.. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google

[algogeeks] Re: Finding repeated element in most efficient way

http://en.wikipedia.org/wiki/Pigeonhole_sortI think it was the repliers intention. But i think it is not the most optimal way of solving the question as the amount of memory it needs in the worst case is higher On Sun, Aug 9, 2009 at 1:47 PM, richa gup

[algogeeks] Re: Finding repeated element in most efficient way

what is this pigeonhole sort ?? 2009/8/9 sharad kumar > use pigeonhole sort > > > On Sun, Aug 9, 2009 at 12:47 PM, richa gupta wrote: > >> Hi, >> An array consists of all unique integers but one. The repeated element >> repeats in the order of two i.e. the repeated integer is 2, 4, 8, 16, >> etc

[algogeeks] Re: Finding repeated element in most efficient way

use pigeonhole sort On Sun, Aug 9, 2009 at 12:47 PM, richa gupta wrote: > Hi, > An array consists of all unique integers but one. The repeated element > repeats in the order of two i.e. the repeated integer is 2, 4, 8, 16, > etc times in the array. > How to find the repeated element in most effi