Re: [algogeeks] Re: All numbers in Array repeat twice except two
@Dave @Mukesh yaa got it... so simple... i was needlessly making it complex thankyou guys . On Tue, Oct 5, 2010 at 2:09 AM, Dave wrote: > @Coolfrog$: It sounds like you think there are n items in each list, > but the problem statement says that the total number of items in the > lists is n. In your example, n = 12. > > Dave > > On Oct 4, 2:16 pm, "coolfrog$" > wrote: > > @Dave > > yes it help very much...i thank you for these... > > but still one doubt > > > > 1.from first element of each sequence we have made a heap > > 2. now only n-1 element remains in all k seqences. > total (= > k*(n-1)) > > elememts > > 3.*"loop is executed once for each output element = once for each > > element in the input sequences" but there are k sequence... > > so the loop must run for *k*(n-1) and each iteration of for loop > running > > cost to O(log k). > >overall complexity can be > >O(k(n-1)log k).. > > > > plz do correct me Dave > > thanks.. > > > > > > > > > > > > On Mon, Oct 4, 2010 at 11:20 PM, Dave wrote: > > > @Coolfrog$: There must have been a communication gap. > > > The initial heap consists of the first element of each sequence: 2, > > > 17, 6. > > > Looping, we output 2, then replace it in the heap with 3 and restore > > > the heap condition: 3, 17, 6. > > > Output 3, replace it with 4: 4, 17, 6. > > > Output 4, replace it with 5: 5, 17, 6. > > > Output 5. There is nothing left in sequence 1, so the heap now has 2 > > > elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace > > > it with 9: 9, 17. > > > Etc. Etc. > > > Finally, after outputting 15, list 3 is exhausted, and the heap > > > consists of 1 element. At this point, the effect of the loop is that > > > list 2 is output. > > > > > The loop is executed once for each output element = once for each > > > element in the input sequences; i.e., n times. > > > > > Does that help? > > > > > Dave > > > > > On Oct 4, 12:09 pm, "coolfrog$" > > > wrote: > > > > @Dave > > > > 1. if three sequence given are 2,3,4,5 > > > > 17,20,31,50 > > > > 6,9,10,15 > > > > while running we will get 2,3,4,5 as sequence no.1 vanishes form > where to > > > > choose next element. for heap . (algo.??) > > > > 2. > > > > Loop until the heap is empty: > > > >output the top of the heap, > > > >replace it with the next element from the list it came from (if > > > > non-empty, of course), > > > >re-establishing the heap condition.*> O(log k). > > > > > > "**loop is executed n times**" .. i am not getting because we have > > > already > > > > executed loop n-1 times in arranging 3,4,5. **what about rest of > > > elements... > > > > > > Correct me plz > > > > > > Regards...** > > > > * > > > > > > On Mon, Oct 4, 2010 at 7:35 PM, Dave > wrote: > > > > > @saurabh: > > > > > > > For the base conversion problem, simulate long division in base B1 > of > > > > > dividing the number by B2. The remainder is the rightmost digit of > the > > > > > conversion. To get the next digit, divide the quotient from the > first > > > > > long division by B2 to get the remainder. Repeat for successive > digits > > > > > until the quotient is zero. > > > > > > > For the merge problem, assuming ascending order: > > > > > > > form a min-heap from the first items from each list. > > > > > Loop until the heap is empty: > > > > >output the top of the heap, > > > > >replace it with the next element from the list it came from (if > > > > > non-empty, of course), > > > > >re-establishing the heap condition. > > > > > > > The loop is executed n times, and each involves O(k) operations. > > > > > > > Dave > > > > > > > On Oct 4, 7:16 am, saurabh agrawal wrote: > > > > > > hi mukesh...gr8 solutioncan u pls help me with some other > > > questions: > > > > > > --Given an array of n integers find all the inversion pairs in > O(n) > > > > > > Inversion pair is one where a[i]>a[j], i > > > > > > > --Convert a number given in base B1 to a number in base B2 > without > > > using > > > > > any > > > > > > intermediate base > > > > > > > > --You are given k sorted lists with total n inputs in all the > lists > > > > > devise a > > > > > > algorithm to merge them into one single sorted list in O(n logk) > > > > > > > > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta < > > > mukeshgupta.2...@gmail.com > > > > > >wrote: > > > > > > > > > The problem could be solved using xor logic. First take xor of > all > > > the > > > > > > > elements .Doing that we get a value which is xor of the two non > > > > > repeating > > > > > > > elements(as xor of similar values is 0). Now xor of two non > > > repeating > > > > > > > numbers contains bits set at those places where the two numbers > > > differ. > > > > > Now > > > > > > > if we take any set bit of our result and again xor all those > values > > > of > > > > > set > > > > > > > where that bit is set
Re: [algogeeks] Re: All numbers in Array repeat twice except two
@coolfrog:
problem statement says total number of elements is n .so overall complexity
wud be O(n*logk) only. even i had the same doubt initially.
Mukesh Gupta
Delhi College of Engineering
On Tue, Oct 5, 2010 at 12:46 AM, coolfrog$
wrote:
> @Dave
> yes it help very much...i thank you for these...
> but still one doubt
>
> 1.from first element of each sequence we have made a heap
> 2. now only n-1 element remains in all k seqences. > total (= k*(n-1))
> elememts
> 3.*"loop is executed once for each output element = once for each
> element in the input sequences" but there are k sequence...
> so the loop must run for *k*(n-1) and each iteration of for loop running
> cost to O(log k).
>overall complexity can be
>O(k(n-1)log k)..
>
> plz do correct me Dave
> thanks..
>
> On Mon, Oct 4, 2010 at 11:20 PM, Dave wrote:
>
>> @Coolfrog$: There must have been a communication gap.
>> The initial heap consists of the first element of each sequence: 2,
>> 17, 6.
>> Looping, we output 2, then replace it in the heap with 3 and restore
>> the heap condition: 3, 17, 6.
>> Output 3, replace it with 4: 4, 17, 6.
>> Output 4, replace it with 5: 5, 17, 6.
>> Output 5. There is nothing left in sequence 1, so the heap now has 2
>> elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace
>> it with 9: 9, 17.
>> Etc. Etc.
>> Finally, after outputting 15, list 3 is exhausted, and the heap
>> consists of 1 element. At this point, the effect of the loop is that
>> list 2 is output.
>>
>> The loop is executed once for each output element = once for each
>> element in the input sequences; i.e., n times.
>>
>> Does that help?
>>
>> Dave
>>
>> On Oct 4, 12:09 pm, "coolfrog$"
>> wrote:
>> > @Dave
>> > 1. if three sequence given are 2,3,4,5
>> > 17,20,31,50
>> > 6,9,10,15
>> > while running we will get 2,3,4,5 as sequence no.1 vanishes form where
>> to
>> > choose next element. for heap . (algo.??)
>> > 2.
>> > Loop until the heap is empty:
>> >output the top of the heap,
>> >replace it with the next element from the list it came from (if
>> > non-empty, of course),
>> >re-establishing the heap condition.*> O(log k).
>> >
>> > "**loop is executed n times**" .. i am not getting because we have
>> already
>> > executed loop n-1 times in arranging 3,4,5. **what about rest of
>> elements...
>> >
>> > Correct me plz
>> >
>> > Regards...**
>> > *
>> >
>> >
>> >
>> >
>> >
>> > On Mon, Oct 4, 2010 at 7:35 PM, Dave wrote:
>> > > @saurabh:
>> >
>> > > For the base conversion problem, simulate long division in base B1 of
>> > > dividing the number by B2. The remainder is the rightmost digit of the
>> > > conversion. To get the next digit, divide the quotient from the first
>> > > long division by B2 to get the remainder. Repeat for successive digits
>> > > until the quotient is zero.
>> >
>> > > For the merge problem, assuming ascending order:
>> >
>> > > form a min-heap from the first items from each list.
>> > > Loop until the heap is empty:
>> > >output the top of the heap,
>> > >replace it with the next element from the list it came from (if
>> > > non-empty, of course),
>> > >re-establishing the heap condition.
>> >
>> > > The loop is executed n times, and each involves O(k) operations.
>> >
>> > > Dave
>> >
>> > > On Oct 4, 7:16 am, saurabh agrawal wrote:
>> > > > hi mukesh...gr8 solutioncan u pls help me with some other
>> questions:
>> > > > --Given an array of n integers find all the inversion pairs in O(n)
>> > > > Inversion pair is one where a[i]>a[j], i> >
>> > > > --Convert a number given in base B1 to a number in base B2 without
>> using
>> > > any
>> > > > intermediate base
>> >
>> > > > --You are given k sorted lists with total n inputs in all the lists
>> > > devise a
>> > > > algorithm to merge them into one single sorted list in O(n logk)
>> >
>> > > > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta <
>> mukeshgupta.2...@gmail.com
>> > > >wrote:
>> >
>> > > > > The problem could be solved using xor logic. First take xor of all
>> the
>> > > > > elements .Doing that we get a value which is xor of the two non
>> > > repeating
>> > > > > elements(as xor of similar values is 0). Now xor of two non
>> repeating
>> > > > > numbers contains bits set at those places where the two numbers
>> differ.
>> > > Now
>> > > > > if we take any set bit of our result and again xor all those
>> values of
>> > > set
>> > > > > where that bit is set we get first non-repeating value. Taking xor
>> of
>> > > all
>> > > > > those values where that bit is not set gives the another
>> non-repeating
>> > > > > number..
>> > > > > For ex
>> > > > > let a[]={2,3,4,3,2,6}
>> >
>> > > > > xor of all values=0010
>> > > > > Now we need to get any set bit. We can extract the rightmost set
>> bit of
>> > > any
>> > > > > number n by taking ( n & ~(n-1))
>> >
>> > > > > Here 2nd bit is
Re: [algogeeks] Re: All numbers in Array repeat twice except two
@Dave
yes it help very much...i thank you for these...
but still one doubt
1.from first element of each sequence we have made a heap
2. now only n-1 element remains in all k seqences. > total (= k*(n-1))
elememts
3.*"loop is executed once for each output element = once for each
element in the input sequences" but there are k sequence...
so the loop must run for *k*(n-1) and each iteration of for loop running
cost to O(log k).
overall complexity can be
O(k(n-1)log k)..
plz do correct me Dave
thanks..
On Mon, Oct 4, 2010 at 11:20 PM, Dave wrote:
> @Coolfrog$: There must have been a communication gap.
> The initial heap consists of the first element of each sequence: 2,
> 17, 6.
> Looping, we output 2, then replace it in the heap with 3 and restore
> the heap condition: 3, 17, 6.
> Output 3, replace it with 4: 4, 17, 6.
> Output 4, replace it with 5: 5, 17, 6.
> Output 5. There is nothing left in sequence 1, so the heap now has 2
> elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace
> it with 9: 9, 17.
> Etc. Etc.
> Finally, after outputting 15, list 3 is exhausted, and the heap
> consists of 1 element. At this point, the effect of the loop is that
> list 2 is output.
>
> The loop is executed once for each output element = once for each
> element in the input sequences; i.e., n times.
>
> Does that help?
>
> Dave
>
> On Oct 4, 12:09 pm, "coolfrog$"
> wrote:
> > @Dave
> > 1. if three sequence given are 2,3,4,5
> > 17,20,31,50
> > 6,9,10,15
> > while running we will get 2,3,4,5 as sequence no.1 vanishes form where to
> > choose next element. for heap . (algo.??)
> > 2.
> > Loop until the heap is empty:
> >output the top of the heap,
> >replace it with the next element from the list it came from (if
> > non-empty, of course),
> >re-establishing the heap condition.*> O(log k).
> >
> > "**loop is executed n times**" .. i am not getting because we have
> already
> > executed loop n-1 times in arranging 3,4,5. **what about rest of
> elements...
> >
> > Correct me plz
> >
> > Regards...**
> > *
> >
> >
> >
> >
> >
> > On Mon, Oct 4, 2010 at 7:35 PM, Dave wrote:
> > > @saurabh:
> >
> > > For the base conversion problem, simulate long division in base B1 of
> > > dividing the number by B2. The remainder is the rightmost digit of the
> > > conversion. To get the next digit, divide the quotient from the first
> > > long division by B2 to get the remainder. Repeat for successive digits
> > > until the quotient is zero.
> >
> > > For the merge problem, assuming ascending order:
> >
> > > form a min-heap from the first items from each list.
> > > Loop until the heap is empty:
> > >output the top of the heap,
> > >replace it with the next element from the list it came from (if
> > > non-empty, of course),
> > >re-establishing the heap condition.
> >
> > > The loop is executed n times, and each involves O(k) operations.
> >
> > > Dave
> >
> > > On Oct 4, 7:16 am, saurabh agrawal wrote:
> > > > hi mukesh...gr8 solutioncan u pls help me with some other
> questions:
> > > > --Given an array of n integers find all the inversion pairs in O(n)
> > > > Inversion pair is one where a[i]>a[j], i >
> > > > --Convert a number given in base B1 to a number in base B2 without
> using
> > > any
> > > > intermediate base
> >
> > > > --You are given k sorted lists with total n inputs in all the lists
> > > devise a
> > > > algorithm to merge them into one single sorted list in O(n logk)
> >
> > > > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta <
> mukeshgupta.2...@gmail.com
> > > >wrote:
> >
> > > > > The problem could be solved using xor logic. First take xor of all
> the
> > > > > elements .Doing that we get a value which is xor of the two non
> > > repeating
> > > > > elements(as xor of similar values is 0). Now xor of two non
> repeating
> > > > > numbers contains bits set at those places where the two numbers
> differ.
> > > Now
> > > > > if we take any set bit of our result and again xor all those values
> of
> > > set
> > > > > where that bit is set we get first non-repeating value. Taking xor
> of
> > > all
> > > > > those values where that bit is not set gives the another
> non-repeating
> > > > > number..
> > > > > For ex
> > > > > let a[]={2,3,4,3,2,6}
> >
> > > > > xor of all values=0010
> > > > > Now we need to get any set bit. We can extract the rightmost set
> bit of
> > > any
> > > > > number n by taking ( n & ~(n-1))
> >
> > > > > Here 2nd bit is the rightmost set bit.
> >
> > > > > Now when we take xor of all values where 2nd bit is set(this could
> be
> > > done
> > > > > as (a[i] & 0010) , we get 6
> > > > > Taking xor of all values where 2nd bit is not set yields 4.
> >
> > > > > Mukesh Gupta
> > > > > Delhi College of Engineering
> >
> > > > > On Mon, Oct 4, 2010 at 3:17 PM, malli
> wrote:
> >
> > > > >> I have an array. All numbers in
Re: [algogeeks] Re: All numbers in Array repeat twice except two
For base conversion :
int convert(int n,int from,int to)
{
int ret=0,i=0;
while(n>0)
{
ret=ret+(n%to)*pow(from,i++);
n/=to;
}
return ret;
}
Mukesh Gupta
Delhi Technological University
On Mon, Oct 4, 2010 at 11:20 PM, Dave wrote:
> @Coolfrog$: There must have been a communication gap.
> The initial heap consists of the first element of each sequence: 2,
> 17, 6.
> Looping, we output 2, then replace it in the heap with 3 and restore
> the heap condition: 3, 17, 6.
> Output 3, replace it with 4: 4, 17, 6.
> Output 4, replace it with 5: 5, 17, 6.
> Output 5. There is nothing left in sequence 1, so the heap now has 2
> elements: 17, 6. Restore the heap condition: 6, 17. Output 6, replace
> it with 9: 9, 17.
> Etc. Etc.
> Finally, after outputting 15, list 3 is exhausted, and the heap
> consists of 1 element. At this point, the effect of the loop is that
> list 2 is output.
>
> The loop is executed once for each output element = once for each
> element in the input sequences; i.e., n times.
>
> Does that help?
>
> Dave
>
> On Oct 4, 12:09 pm, "coolfrog$"
> wrote:
> > @Dave
> > 1. if three sequence given are 2,3,4,5
> > 17,20,31,50
> > 6,9,10,15
> > while running we will get 2,3,4,5 as sequence no.1 vanishes form where to
> > choose next element. for heap . (algo.??)
> > 2.
> > Loop until the heap is empty:
> >output the top of the heap,
> >replace it with the next element from the list it came from (if
> > non-empty, of course),
> >re-establishing the heap condition.*> O(log k).
> >
> > "**loop is executed n times**" .. i am not getting because we have
> already
> > executed loop n-1 times in arranging 3,4,5. **what about rest of
> elements...
> >
> > Correct me plz
> >
> > Regards...**
> > *
> >
> >
> >
> >
> >
> > On Mon, Oct 4, 2010 at 7:35 PM, Dave wrote:
> > > @saurabh:
> >
> > > For the base conversion problem, simulate long division in base B1 of
> > > dividing the number by B2. The remainder is the rightmost digit of the
> > > conversion. To get the next digit, divide the quotient from the first
> > > long division by B2 to get the remainder. Repeat for successive digits
> > > until the quotient is zero.
> >
> > > For the merge problem, assuming ascending order:
> >
> > > form a min-heap from the first items from each list.
> > > Loop until the heap is empty:
> > >output the top of the heap,
> > >replace it with the next element from the list it came from (if
> > > non-empty, of course),
> > >re-establishing the heap condition.
> >
> > > The loop is executed n times, and each involves O(k) operations.
> >
> > > Dave
> >
> > > On Oct 4, 7:16 am, saurabh agrawal wrote:
> > > > hi mukesh...gr8 solutioncan u pls help me with some other
> questions:
> > > > --Given an array of n integers find all the inversion pairs in O(n)
> > > > Inversion pair is one where a[i]>a[j], i >
> > > > --Convert a number given in base B1 to a number in base B2 without
> using
> > > any
> > > > intermediate base
> >
> > > > --You are given k sorted lists with total n inputs in all the lists
> > > devise a
> > > > algorithm to merge them into one single sorted list in O(n logk)
> >
> > > > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta <
> mukeshgupta.2...@gmail.com
> > > >wrote:
> >
> > > > > The problem could be solved using xor logic. First take xor of all
> the
> > > > > elements .Doing that we get a value which is xor of the two non
> > > repeating
> > > > > elements(as xor of similar values is 0). Now xor of two non
> repeating
> > > > > numbers contains bits set at those places where the two numbers
> differ.
> > > Now
> > > > > if we take any set bit of our result and again xor all those values
> of
> > > set
> > > > > where that bit is set we get first non-repeating value. Taking xor
> of
> > > all
> > > > > those values where that bit is not set gives the another
> non-repeating
> > > > > number..
> > > > > For ex
> > > > > let a[]={2,3,4,3,2,6}
> >
> > > > > xor of all values=0010
> > > > > Now we need to get any set bit. We can extract the rightmost set
> bit of
> > > any
> > > > > number n by taking ( n & ~(n-1))
> >
> > > > > Here 2nd bit is the rightmost set bit.
> >
> > > > > Now when we take xor of all values where 2nd bit is set(this could
> be
> > > done
> > > > > as (a[i] & 0010) , we get 6
> > > > > Taking xor of all values where 2nd bit is not set yields 4.
> >
> > > > > Mukesh Gupta
> > > > > Delhi College of Engineering
> >
> > > > > On Mon, Oct 4, 2010 at 3:17 PM, malli
> wrote:
> >
> > > > >> I have an array. All numbers in the array repeat twice except two
> > > > >> numbers which repeat only once. All the numbers are placed
> randomly.
> > > > >> Goal is to find out efficiently the two numbers that have not
> > > > >> repeated with O(1) extra memory. Expecting linear solution.
> >
> > > > >> --
> > > > >> You received this message because
Re: [algogeeks] Re: All numbers in Array repeat twice except two
@Dave
1. if three sequence given are 2,3,4,5
17,20,31,50
6,9,10,15
while running we will get 2,3,4,5 as sequence no.1 vanishes form where to
choose next element. for heap . (algo.??)
2.
Loop until the heap is empty:
output the top of the heap,
replace it with the next element from the list it came from (if
non-empty, of course),
re-establishing the heap condition.*> O(log k).
"**loop is executed n times**" .. i am not getting because we have already
executed loop n-1 times in arranging 3,4,5. **what about rest of elements...
Correct me plz
Regards...**
*
On Mon, Oct 4, 2010 at 7:35 PM, Dave wrote:
> @saurabh:
>
> For the base conversion problem, simulate long division in base B1 of
> dividing the number by B2. The remainder is the rightmost digit of the
> conversion. To get the next digit, divide the quotient from the first
> long division by B2 to get the remainder. Repeat for successive digits
> until the quotient is zero.
>
> For the merge problem, assuming ascending order:
>
> form a min-heap from the first items from each list.
> Loop until the heap is empty:
>output the top of the heap,
>replace it with the next element from the list it came from (if
> non-empty, of course),
>re-establishing the heap condition.
>
> The loop is executed n times, and each involves O(k) operations.
>
> Dave
>
>
> On Oct 4, 7:16 am, saurabh agrawal wrote:
> > hi mukesh...gr8 solutioncan u pls help me with some other questions:
> > --Given an array of n integers find all the inversion pairs in O(n)
> > Inversion pair is one where a[i]>a[j], i >
> > --Convert a number given in base B1 to a number in base B2 without using
> any
> > intermediate base
> >
> > --You are given k sorted lists with total n inputs in all the lists
> devise a
> > algorithm to merge them into one single sorted list in O(n logk)
> >
> > On Mon, Oct 4, 2010 at 5:31 PM, Mukesh Gupta >wrote:
> >
> >
> >
> >
> >
> > > The problem could be solved using xor logic. First take xor of all the
> > > elements .Doing that we get a value which is xor of the two non
> repeating
> > > elements(as xor of similar values is 0). Now xor of two non repeating
> > > numbers contains bits set at those places where the two numbers differ.
> Now
> > > if we take any set bit of our result and again xor all those values of
> set
> > > where that bit is set we get first non-repeating value. Taking xor of
> all
> > > those values where that bit is not set gives the another non-repeating
> > > number..
> > > For ex
> > > let a[]={2,3,4,3,2,6}
> >
> > > xor of all values=0010
> > > Now we need to get any set bit. We can extract the rightmost set bit of
> any
> > > number n by taking ( n & ~(n-1))
> >
> > > Here 2nd bit is the rightmost set bit.
> >
> > > Now when we take xor of all values where 2nd bit is set(this could be
> done
> > > as (a[i] & 0010) , we get 6
> > > Taking xor of all values where 2nd bit is not set yields 4.
> >
> > > Mukesh Gupta
> > > Delhi College of Engineering
> >
> > > On Mon, Oct 4, 2010 at 3:17 PM, malli wrote:
> >
> > >> I have an array. All numbers in the array repeat twice except two
> > >> numbers which repeat only once. All the numbers are placed randomly.
> > >> Goal is to find out efficiently the two numbers that have not
> > >> repeated with O(1) extra memory. Expecting linear solution.
> >
> > >> --
> > >> You received this message because you are subscribed to the Google
> Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algoge...@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 algoge...@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.- Hide quoted text -
> >
> > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@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.
>
>
--
*Divesh*
(¨`·.·´¨) Always
`·.¸(¨`·.·´¨ ) Keep
(¨`·.·´¨)¸.·´Smiling!
`·.¸.·´" Life can give u 100's of reason 2cry,but u can give life 1000's
of reasons 2Smile"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to al
