Re: [algogeeks] Re: Single linked list questions.
@aditya, Who said it's a Y shaped structure, It can very well has a cycle. Assume the case when the last node is not pointing to NULL but to a node in the list. On Thu, Jan 6, 2011 at 7:45 PM, ADITYA KUMAR wrote: > @vishal > saurabh is right > its merging at only one point its a Y-shaped structure > > > > On Thu, Jan 6, 2011 at 7:29 PM, vishal raja wrote: > >> >> @sourabh, >> In addition to your solution, If there is any cycle(loop) exist in the >> link list your algo will fail. >> To solve this problem first detect this cycle if there is any and count >> the element in the cycle, and then you can do the mathematics. >> >> >> >> On Thu, Jan 6, 2011 at 6:51 PM, sourabh jakhar >> wrote: >> >>> for second question calculate the difference in length of two linked >>> list. >>> and than shift the head of longest linked list to the calculated >>> difference. while the head of shorest is at the first node of that linked >>> list. >>> Than iterate both to see if info is equal and that is the merging point. >>> complexity-o(n). >>> hope this help >>> >>> >>> On Thu, Jan 6, 2011 at 6:48 PM, juver++ wrote: >>> >>>> Yes, but recursion stack's size is limited instead of iterative version. >>>> >>>> >>>> -- >>>> 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. >>>> >>> >>> >>> >>> -- >>> SOURABH JAKHAR,(CSE)(3 year) >>> ROOM NO 167 , >>> TILAK,HOSTEL >>> 'MNNIT ALLAHABAD >>> >>> >>> The Law of Win says, "Let's not do it your way or my way; let's do it the >>> best way." >>> >>> -- >>> 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. >> > > > > -- > Regards > Aditya Kumar > B-tech 3rd year > Computer Science & Engg. > MNNIT, Allahabad. > > -- > 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.
Re: [algogeeks] Re: Single linked list questions.
@sourabh, In addition to your solution, If there is any cycle(loop) exist in the link list your algo will fail. To solve this problem first detect this cycle if there is any and count the element in the cycle, and then you can do the mathematics. On Thu, Jan 6, 2011 at 6:51 PM, sourabh jakhar wrote: > for second question calculate the difference in length of two linked list. > and than shift the head of longest linked list to the calculated > difference. while the head of shorest is at the first node of that linked > list. > Than iterate both to see if info is equal and that is the merging point. > complexity-o(n). > hope this help > > > On Thu, Jan 6, 2011 at 6:48 PM, juver++ wrote: > >> Yes, but recursion stack's size is limited instead of iterative version. >> >> -- >> 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. >> > > > > -- > SOURABH JAKHAR,(CSE)(3 year) > ROOM NO 167 , > TILAK,HOSTEL > 'MNNIT ALLAHABAD > > > The Law of Win says, "Let's not do it your way or my way; let's do it the > best way." > > -- > 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.
Re: [algogeeks] Divide an array into two equal subsets
This means , You can make a sum = j , with or without using the item i , while calculating P[i][j]. So you can have another counter Count2 which will have the count for such items. So you will calculate P as discussed before but You will add 1 in Count2[i][j] whenever you find that case. add one in count[i][j] in any of P = 1 case. in the end you'll search for the max value of j (closest to S/2) for all P values which has this property on value of i . 1. i = 50 2. for all i> 50 i-count2[i][j] <= 50 I think this will do. Check it out. On Thu, Dec 30, 2010 at 12:41 PM, Ankur Khurana wrote: > vishal , what will we do to count when both p[i-1][j] and > p[i-1][j-a[i]] is true . > > On Thu, Dec 30, 2010 at 12:36 PM, Ankur Khurana > wrote: > > Thanks everybody for wonderful support and special thanks to Vishal > > raja. . But i was bit apprehensive about your last solution . . i will > > test it :) and let you know as well . Thanks . . . . > > > > > > On Thu, Dec 30, 2010 at 11:52 AM, vishal raja > wrote: > >> But the same solution I've given above can give you the solution for > this > >> problem . > >> In the formed table of P[i][j] , you can take another variable attached > to > >> it as count[i][j] for how many items we have selected yet. > >> So you gotta find , the max. value of j which has count = 50. > >> count[i][j] = count[i-1][j] if P(i-1,j) ==1 > >> count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 > >> else count[i][j] = 0 > >> > >> > >> > >> > >> On Thu, Dec 30, 2010 at 11:42 AM, vishal raja > >> wrote: > >>> > >>> yeah, My bad. > >>> Missed that. > >>> > >>> On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares < > wladimir...@gmail.com> > >>> wrote: > >>>> > >>>> Sum up all the number and divide by 2 > >>>> > >>>> Using the algorithm subset problem to find a number close to median > >>>> > >>>> > >>>> Wladimir Araujo Tavares > >>>> Federal University of Ceará > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> > >>>> On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana < > ankur.kkhur...@gmail.com> > >>>> wrote: > >>>>> > >>>>> How will you divide and array of approx 100 elements into two sub > sets > >>>>> of 50 each such that the difference between both the subsets is the > >>>>> minimum possible one . . > >>>>> > >>>>> Thanks in advance . > >>>>> Ankur > >>>>> > >>>>> -- > >>>>> 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. > >>> > >> > >> -- > >> 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. > > -- 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.
Re: [algogeeks] Divide an array into two equal subsets
But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja wrote: > yeah, My bad. > Missed that. > > On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares < > wladimir...@gmail.com> wrote: > >> Sum up all the number and divide by 2 >> >> Using the algorithm subset problem to find a number close to median >> >> >> Wladimir Araujo Tavares >> *Federal University of Ceará >> >> * >> >> >> >> >> >> On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana >> wrote: >> >>> How will you divide and array of approx 100 elements into two sub sets >>> of 50 each such that the difference between both the subsets is the >>> minimum possible one . . >>> >>> Thanks in advance . >>> Ankur >>> >>> -- >>> 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. >> > > -- 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.
Re: [algogeeks] Divide an array into two equal subsets
yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wrote: > Sum up all the number and divide by 2 > > Using the algorithm subset problem to find a number close to median > > > Wladimir Araujo Tavares > *Federal University of Ceará > > * > > > > > > On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana > wrote: > >> How will you divide and array of approx 100 elements into two sub sets >> of 50 each such that the difference between both the subsets is the >> minimum possible one . . >> >> Thanks in advance . >> Ankur >> >> -- >> 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. > -- 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.
Re: [algogeeks] Divide an array into two equal subsets
use dynamic programming.
Make this problem similar to knapsack one.
You want to find the items from a given array which sums up to (exactly or
nearly) S/2 (here S is total sum of all integers)
Let's say
P(i,j) is probability to make a sum = j with the first i items in the array.
P(i,j) = 1 if P(i-1,j) ==1 || P(i-1,j-a[i]) == 1 else 0
So you can rewrite it as
P(i,j) = max { P(i-1,j) , P(i-1,j-a[i]) }
you would like to calculate values of P
from i=1, j=1 to i=size_of_array , j = S/2
then find the max value of j for which value of P is 1. time complexity will
be O(nS) and same is the space complexity
That's it.
On Wed, Dec 29, 2010 at 10:37 PM, Ankur Khurana wrote:
> How will you divide and array of approx 100 elements into two sub sets
> of 50 each such that the difference between both the subsets is the
> minimum possible one . .
>
> Thanks in advance .
> Ankur
>
> --
> 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.
Re: [algogeeks] Re: combinations problem
@juver, ofcourse , and that's not a big deal. On Wed, Dec 29, 2010 at 5:11 PM, juver++ wrote: > Yes, it's true. But we should process DP in the following order not to take > one element more than once. > > -- > 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.
Re: [algogeeks] Re: combinations problem
i think we don't need to store the total no. of occurance of any character. we can think of it as a classic knapSack, We have n ( size of the string) items, does'nt matter if they repeat or not . We don't have to keep a track how many of a char we have used as we have only options in this array , just take every index item as different item, that will automatcally do this. On Wed, Dec 29, 2010 at 4:46 PM, juver++ wrote: > It's a knapsack problem with bounds. Solve it using DP - for each state > keep number of used characters and preserve to exceed the bounds. > > -- > 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.
Re: [algogeeks] Re: combinations problem
What's the relation with the given string. I could'nt get you completely. On Wed, Dec 29, 2010 at 4:18 PM, suhash wrote: > Is'nt this just a knapsack problem! > > On Dec 29, 3:45 pm, rajeev kumar wrote: > > you are given a string.It may have repeated characters.each character has > > it's own weight.find combination of characters whose sum value is equal > to > > given value. > > > > ex: given string 'abcbacbabcc' > > weight of each character a-5,b-4,c-6. > > > > character combination which gives sum 15 is 'aaa' > > > > -- > > Thank You > > -- > 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.
Re: [algogeeks] Re: In place sorting
Perform simple merging taking the ends of the list. So You compare the last elements of both the list which ever is larger you copy that at the end of the first array and so on. you got to maintain three pointer , two for the lists and the third one for the position it should be placed. time complexity will be O(m+n) On Wed, Dec 29, 2010 at 2:55 PM, monty 1987 <1986mo...@gmail.com> wrote: > hi , > this is not a research kind of problem i expect a simple answer. > > > On Wed, Dec 29, 2010 at 2:33 PM, juver++ wrote: > >> Use inplace merge algorithms along with merge sort. >> http://www.logiccoder.com/Downloads/krnrd20.pdf >> >> -- >> 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. > -- 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.
Re: [algogeeks] Answer This
There were 20 green eyed people and they will commit suicide on 20th day altogether. See, There is atleast one green-eyed man. So let's take the case if there was only one gree-eyed man. than that man could've seen the colour of all other blued-eyed people and commit suicide on the very first day. if there were two of them, then these two guys can see each other as green-eyed guy, they wait for a day , on the second day they realize that there must be one more green-wyed guy other than than that guy . so it goes like that , and using same iteration we can see if there are n green-eyed people , they will all commit suicide altogether on n-th day. -- 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.
Re: [algogeeks] Arrays
add up all the elements in array A say sumA and array B say sumB ,substract the sumA from sumB... You'll get the element. On Tue, Sep 21, 2010 at 5:36 AM, Anand wrote: > Two unsorted arrays are given A[n] and B[n+1]. Array A contains n integers > and B contains n+1 integers of which n are same as in array B but in > different order and one extra element x. Write an optimized algorithm to > find the value of element x. Use only one pass of both arrays A and B. > > -- > 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.
Re: [algogeeks] Yahoo!!!! Puzzle
take out that one A pill that's there in the jar. take the half of all the four pills, that's how u'll make sure that u've had 1 of 'A' and 1 of 'B' pill. On Tue, Sep 14, 2010 at 2:52 PM, bittu wrote: > You are on a strict medical regimen that requires you to take two > types of pills each day. You must take exactly one A pill and exactly > one B pill at the same time. The pills are very expensive, and you > don't want to waste any. So you open the bottle of A pills, and tap > one out into your hand. Then you open the bottle of B pills and do the > same thing -- but you make a mistake, and two B pills come out into > your hand with the A pill. But the pills are all exactly identical. > There is no way to tell A pills apart from B pills. How can you > satisfy your regimen and take exactly one of each pill at the same > time, without wasting any pills? > > > Write Algorithm to Solve dis Problem in constant time..isn't it..??? > > > > > > Regard's > Shashank Mani Narayan " Don't Be Evil U Can Earn While U learn" > Computer Science & Engineering > Birla Institute of Technology,Mesra > Cell No. +91-9166674831 > > -- > 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.
