[algogeeks] Re: Link list Q
This is known as the "tortoise and hare" algorithm. Imagine p is
running ahead of the q pointer, at a certain point they will meet
inside a loop if it exists.
On Dec 1, 3:12 am, Vijay Khandar wrote:
> What does the following program do on the singly linked list?
>
> p=head;
> q=head->next;
> while(p!=null && q!null)
> {
> if(p==q)
> {
> exit(0)}
>
> p=p->next;
> q=(q->next)?(q->next->next):q->next;
>
> }
>
> a)traverse the entire singly linked list
> b)detects the duplicate nodes
> c)detects the loop in singly linked list
> d)detects the duplicate nodes at alternate places
>
> plz explain anyone with correct option..
--
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.
Re: [algogeeks] Link list Q
simple way of understanding this algo is that , q is incremented twice than p or you can say q is moving twice faster then p. consider a scenario where last_node-> = first_node. now q would complete 2 round of this single link before node p reaches last_node . so when p reaches last_node , at that point of time q would have reached last_node (hence completing this 2 circle). hope this will help you in understanding the idea. On Fri, Dec 2, 2011 at 12:14 PM, Vijay Khandar wrote: > But how plz explain in detail.. > > > On Thu, Dec 1, 2011 at 8:14 PM, Karthikeyan V.B wrote: > >> detects the loop in the linked list >> >> -- >> 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. > -- 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.
Re: [algogeeks] Link list Q
But how plz explain in detail.. On Thu, Dec 1, 2011 at 8:14 PM, Karthikeyan V.B wrote: > detects the loop in the linked list > > -- > 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.
[algogeeks] Re: Removing Duplicates In array and Linked list
Please help me in solving above quesitons On 1 December 2011 08:33, kumar raja wrote: > 1) In there any way to remove duplicates in Integer array in linear time > using constant space?? > > i dont want the Hash based solution > > > 2) Is there anyway to remove the duplicates elements from an unsorted > linked list in * Single Pass*??? > > > > > -- > Regards > Kumar Raja > M.Tech(SIT) > IIT Kharagpur, > 10it60...@iitkgp.ac.in > > > -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Removing Duplicates In array and Linked list
Hi, Create a binary search tree with elements , while inserting check for equal elements and delete it. But for insertion of n elements in a BST takes O(nlogn) -- 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.
[algogeeks] smallest segment in a document containing all the given words
An idea is to start with a heap of size k. Its tricky how to keep track of the start and end indices of the smallest length. Do not enter a duplicate element in the heap. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/XbqIrf1Z6MUJ. 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.
[algogeeks] Re: Reverse a XOR linked list in O(1) time ?
Nodes of these XOR lists look like
typedef struct {
PTRS_AS_INT next_xor_prev;
DATA data;
} NODE;
You need 2 pointers to adjacent nodes to traverse. If p and q are
these pointers, then to advance to the next node,
tmp = p;
p = q ^ p->next_xor_prev; // not correct C; add casts to make it
work.
q = tmp;
This code is identical regardless of traversal direction. Initialize
with p as the next element "after" q, and the advance goes "forward."
Initialize with p as the previous element "before" q, and the advance
is in reverse.
This a convenient implementation is circular with the list header
containing a head and tail pointer. To traverse forward, initialize
the above with
p = header->head;
q = header->tail;
and to go backward
p = header->tail;
q = header ->head;
Now it's obvious that to reverse the list you need only swap the head
and tail pointers. There's no other way to do it.
You can reverse a regular doubly linked list in O(1) with the same
idea. Define nodes as
typedef struct node_s {
struct node_s *ptrs[2];
DATA data;
} NODE;
In the list header, keep a bit that says 0) whether ptrs[0] is "next"
and ptrs[1] is "prev" or 1) the opposite. Flipping this bit reverses
the list.
On Nov 30, 8:32 pm, Rajeev Kumar wrote:
> --
> Thank You
> Rajeev Kumar
--
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.
[algogeeks] Re: Sub-array problem
@ankit...
I don't think the algorithm is correct...
The check "max_ending_here < 0 && max_limit_here <=k" doesn't look
correct...
Also I am not able to figure out the importance of 0 in the check ..
Ankit, may be I am wrong. Hence, can you come up with the algorithm
explaining ( with a set of steps ) what you are doing here...
On Dec 1, 11:12 pm, atul anand wrote:
> @ankit : sorry dude , its not working for given input
>
> {2,1,3,4,5} k=12,
> ans=12, sub-array={3,4,5}
>
> your algo will give ans=10 sub-array{0 to 3}
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha wrote:
> > A little variation of kadane's algo will do as written below: -
>
> > #include "stdafx.h"
> > #include "stdlib.h"
>
> > int _tmain(int argc, _TCHAR* argv[])
> > {
> > int a[5] = {-1,3,1,2,-3};
> > int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0
> > ,
> > endIndex = 0, itr = 0;
> > int k=12;
> > for (itr = 0; itr<5;itr++)
> > {
> > max_ending_here +=a[itr];
> > if (max_ending_here < 0 && max_limit_here <=k)
> > {
> > max_ending_here = 0;
> > startIndex++;
> > }
> > else if (max_so_far > {
> > if (max_ending_here <= k)
> > {
> > max_so_far = max_ending_here;
> > endIndex = itr;
> > }
> > else
> > {
> > max_limit_here = max_ending_here;
> > max_ending_here = 0;
>
> > }
> > }
>
> > }
>
> > printf("%d%d%d", max_so_far, startIndex, endIndex);
> > system("PAUSE");
> > return 0;
> > }
> > Complexity O(n)
>
> > Cheers,
> > Ankit Sinha
> > On Thu, Dec 1, 2011 at 4:58 PM, sourabh wrote:
> > > @atul...
> > > thanks dude for ur thorough screening of the algo and pointing out the
> > > mistakes... I think that's y its always said that until and unless we
> > > don't turn an algo to a working code we are never really sure whether
> > > its perfect and covers all the cases.
>
> > > On Dec 1, 4:23 pm, atul anand wrote:
> > >> yup i made some calculation error
>
> > >> Now this algo works perfectly :) :)
>
> > >> Thanks for your help and explanation :) :)
>
> > >> On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
> > >> > @atul ...
>
> > >> > Reply 1:
> > >> > Yes, you are correct.. i missed it... Correct statement is as follows:
>
> > >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> > >> > i = 3, j = 4
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > >> > =5 , i = 4, j = 4
>
> > >> > -
>
> > >> > Reply 2:
> > >> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
> > >> > not getting my point even if 14 is the search element, still the
> > >> > element smaller than equal to 14 in array B is 10 and not 15...
>
> > >> > Hence, the above calculation that you have made are incorrect.
>
> > >> > If you look at the problem statement it says that we have to find the
> > >> > sum which is smaller than equal to X.
> > >> > Now, if you look ta ur calculations you will see that your 'closest to
> > >> > X' search space contains elements 13 which is invalid as it is greater
> > >> > than 12...
>
> > >> > Hence, i m re-calculating the values based on the above given
> > >> > algorithm...
>
> > >> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> > >> > 8 , i = 1, j = 3
>
> > >> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > >> > =12 , i = 2, j = 4
>
> > >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > >> > 9 , i = 3 , j = 4
>
> > >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> > >> > 5 , i = 4 , j = 4
>
> > >> > Also, as calculated in the previous post the corner case gives 10 as
> > >> > the closest to X.
>
> > >> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> > >> > 12.
>
> > >> > On Dec 1, 2:52 pm, atul anand wrote:
> > >> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> > >> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 =
> > 13 ,
> > >> > i
> > >> > > = 1, j = 4
> > >> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > =12 ,
> > >> > i
> > >> > > = 2, j = 4
> > >> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > 11
> > >> > , i
> > >> > > = 3 , j = 4
> > >> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > = 5 ,
> > >> > i
> > >> > > = 4 , j = 4
>
> > >> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is
> > 12) .
> > >> > > So basically among this
Re: [algogeeks] Re: Sub-array problem
@ankit : sorry dude , its not working for given input
{2,1,3,4,5} k=12,
ans=12, sub-array={3,4,5}
your algo will give ans=10 sub-array{0 to 3}
On Thu, Dec 1, 2011 at 11:33 PM, Ankit Sinha wrote:
> A little variation of kadane's algo will do as written below: -
>
> #include "stdafx.h"
> #include "stdlib.h"
>
> int _tmain(int argc, _TCHAR* argv[])
> {
>int a[5] = {-1,3,1,2,-3};
>int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0
> ,
> endIndex = 0, itr = 0;
>int k=12;
>for (itr = 0; itr<5;itr++)
>{
>max_ending_here +=a[itr];
>if (max_ending_here < 0 && max_limit_here <=k)
>{
>max_ending_here = 0;
>startIndex++;
>}
>else if (max_so_far {
>if (max_ending_here <= k)
>{
>max_so_far = max_ending_here;
>endIndex = itr;
>}
>else
>{
>max_limit_here = max_ending_here;
>max_ending_here = 0;
>
>}
>}
>
>}
>
>printf("%d%d%d", max_so_far, startIndex, endIndex);
>system("PAUSE");
>return 0;
> }
> Complexity O(n)
>
> Cheers,
> Ankit Sinha
> On Thu, Dec 1, 2011 at 4:58 PM, sourabh wrote:
> > @atul...
> > thanks dude for ur thorough screening of the algo and pointing out the
> > mistakes... I think that's y its always said that until and unless we
> > don't turn an algo to a working code we are never really sure whether
> > its perfect and covers all the cases.
> >
> > On Dec 1, 4:23 pm, atul anand wrote:
> >> yup i made some calculation error
> >>
> >> Now this algo works perfectly :) :)
> >>
> >> Thanks for your help and explanation :) :)
> >>
> >>
> >>
> >>
> >>
> >>
> >>
> >> On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
> >> > @atul ...
> >>
> >> > Reply 1:
> >> > Yes, you are correct.. i missed it... Correct statement is as follows:
> >>
> >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> >> > i = 3, j = 4
> >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> >> > =5 , i = 4, j = 4
> >>
> >> > -
> >>
> >> > Reply 2:
> >> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
> >> > not getting my point even if 14 is the search element, still the
> >> > element smaller than equal to 14 in array B is 10 and not 15...
> >>
> >> > Hence, the above calculation that you have made are incorrect.
> >>
> >> > If you look at the problem statement it says that we have to find the
> >> > sum which is smaller than equal to X.
> >> > Now, if you look ta ur calculations you will see that your 'closest to
> >> > X' search space contains elements 13 which is invalid as it is greater
> >> > than 12...
> >>
> >> > Hence, i m re-calculating the values based on the above given
> >> > algorithm...
> >>
> >> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> >> > 8 , i = 1, j = 3
> >>
> >> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> >> > =12 , i = 2, j = 4
> >>
> >> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> >> > 9 , i = 3 , j = 4
> >>
> >> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> >> > 5 , i = 4 , j = 4
> >>
> >> > Also, as calculated in the previous post the corner case gives 10 as
> >> > the closest to X.
> >>
> >> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> >> > 12.
> >>
> >> > On Dec 1, 2:52 pm, atul anand wrote:
> >> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
> >>
> >> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 =
> 13 ,
> >> > i
> >> > > = 1, j = 4
> >> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> =12 ,
> >> > i
> >> > > = 2, j = 4
> >> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> 11
> >> > , i
> >> > > = 3 , j = 4
> >> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> = 5 ,
> >> > i
> >> > > = 4 , j = 4
> >>
> >> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is
> 12) .
> >> > > So basically among this we have to find element closest X ( where
> >> > element <
> >> > > = X )
> >> > > hence 12 is the answer.
> >>
> >> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand >
> >> > wrote:
> >> > > > @sourabh
> >>
> >> > > > i guess you need to modify this statement :-
> >>
> >> > > > 3) Now for each element B[i][0] , do a (modified) binary *search
> for
> >> > > > the closest value smaller than equal to (X + B[i][0])* in array
> B[i
> >> > > > +1... n][0] ,
> >> > > > Say the found index after binary search is
Re: [algogeeks] Re: Sub-array problem
A little variation of kadane's algo will do as written below: -
#include "stdafx.h"
#include "stdlib.h"
int _tmain(int argc, _TCHAR* argv[])
{
int a[5] = {-1,3,1,2,-3};
int max_so_far= 0, max_ending_here= 0,max_limit_here=0,startIndex=0 ,
endIndex = 0, itr = 0;
int k=12;
for (itr = 0; itr<5;itr++)
{
max_ending_here +=a[itr];
if (max_ending_here < 0 && max_limit_here <=k)
{
max_ending_here = 0;
startIndex++;
}
else if (max_so_far wrote:
> @atul...
> thanks dude for ur thorough screening of the algo and pointing out the
> mistakes... I think that's y its always said that until and unless we
> don't turn an algo to a working code we are never really sure whether
> its perfect and covers all the cases.
>
> On Dec 1, 4:23 pm, atul anand wrote:
>> yup i made some calculation error
>>
>> Now this algo works perfectly :) :)
>>
>> Thanks for your help and explanation :) :)
>>
>>
>>
>>
>>
>>
>>
>> On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
>> > @atul ...
>>
>> > Reply 1:
>> > Yes, you are correct.. i missed it... Correct statement is as follows:
>>
>> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
>> > i = 3, j = 4
>> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
>> > =5 , i = 4, j = 4
>>
>> > -
>>
>> > Reply 2:
>> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
>> > not getting my point even if 14 is the search element, still the
>> > element smaller than equal to 14 in array B is 10 and not 15...
>>
>> > Hence, the above calculation that you have made are incorrect.
>>
>> > If you look at the problem statement it says that we have to find the
>> > sum which is smaller than equal to X.
>> > Now, if you look ta ur calculations you will see that your 'closest to
>> > X' search space contains elements 13 which is invalid as it is greater
>> > than 12...
>>
>> > Hence, i m re-calculating the values based on the above given
>> > algorithm...
>>
>> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
>> > 8 , i = 1, j = 3
>>
>> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
>> > =12 , i = 2, j = 4
>>
>> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
>> > 9 , i = 3 , j = 4
>>
>> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
>> > 5 , i = 4 , j = 4
>>
>> > Also, as calculated in the previous post the corner case gives 10 as
>> > the closest to X.
>>
>> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
>> > 12.
>>
>> > On Dec 1, 2:52 pm, atul anand wrote:
>> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>>
>> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 ,
>> > i
>> > > = 1, j = 4
>> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
>> > i
>> > > = 2, j = 4
>> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11
>> > , i
>> > > = 3 , j = 4
>> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 ,
>> > i
>> > > = 4 , j = 4
>>
>> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
>> > > So basically among this we have to find element closest X ( where
>> > element <
>> > > = X )
>> > > hence 12 is the answer.
>>
>> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand
>> > wrote:
>> > > > @sourabh
>>
>> > > > i guess you need to modify this statement :-
>>
>> > > > 3) Now for each element B[i][0] , do a (modified) binary *search for
>> > > > the closest value smaller than equal to (X + B[i][0])* in array B[i
>> > > > +1... n][0] ,
>> > > > Say the found index after binary search is j ( which is > i)...
>>
>> > > > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,
>> > i
>> > > > = 1, j = 3
>> > > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
>> > i =
>> > > > 2, j = 4
>> > > > 12 + 6 = 18 , closest element found = *no element found ??? how *
>>
>> > > > *Cumulative SUM*
>>
>> > > > *i*
>>
>> > > > 2
>>
>> > > > 0
>>
>> > > > 3
>>
>> > > > 1
>>
>> > > > 6
>>
>> > > > 2
>>
>> > > > 10
>>
>> > > > 3
>>
>> > > > *15*
>>
>> > > > 4
>>
>> > > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
>> > > > ..right ??
>>
>> > --
>> > 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 t
[algogeeks] Removing Duplicates In array and Linked list
1) In there any way to remove duplicates in Integer array in linear time using constant space?? i dont want the Hash based solution 2) Is there anyway to remove the duplicates elements from an unsorted linked list in * Single Pass*??? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- 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.
Re: [algogeeks] Link list Q
detects the loop in the linked list -- 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.
[algogeeks] Re : Nim Game
can anyone tell how to detect cycles in the game of nim ?
for eg. if there are x coins, and two players are taking out coins
alternatively, such that the one who has no choice loses... and the
number of coins allowed to take in one go are {2, 4, 5}, then the whole
cycle is repeating after 7... for 1st player --
result - L W W W W W L | L W W W W W L | L W W W
coins - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...
similarly for choices {3, 5}
i am getting a cycle of length 8...
how would i come to know as to when it will start repeating ?
Disclaimer : not my question, copied from net
--
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.
[algogeeks] Re: Sub-array problem
@atul...
thanks dude for ur thorough screening of the algo and pointing out the
mistakes... I think that's y its always said that until and unless we
don't turn an algo to a working code we are never really sure whether
its perfect and covers all the cases.
On Dec 1, 4:23 pm, atul anand wrote:
> yup i made some calculation error
>
> Now this algo works perfectly :) :)
>
> Thanks for your help and explanation :) :)
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
> > @atul ...
>
> > Reply 1:
> > Yes, you are correct.. i missed it... Correct statement is as follows:
>
> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> > i = 3, j = 4
> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> > =5 , i = 4, j = 4
>
> > -
>
> > Reply 2:
> > I might be wrong in calculating 12 + 2 = 14 but i guess you are
> > not getting my point even if 14 is the search element, still the
> > element smaller than equal to 14 in array B is 10 and not 15...
>
> > Hence, the above calculation that you have made are incorrect.
>
> > If you look at the problem statement it says that we have to find the
> > sum which is smaller than equal to X.
> > Now, if you look ta ur calculations you will see that your 'closest to
> > X' search space contains elements 13 which is invalid as it is greater
> > than 12...
>
> > Hence, i m re-calculating the values based on the above given
> > algorithm...
>
> > 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> > 8 , i = 1, j = 3
>
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> > =12 , i = 2, j = 4
>
> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> > 9 , i = 3 , j = 4
>
> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> > 5 , i = 4 , j = 4
>
> > Also, as calculated in the previous post the corner case gives 10 as
> > the closest to X.
>
> > Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> > 12.
>
> > On Dec 1, 2:52 pm, atul anand wrote:
> > > and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> > > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 ,
> > i
> > > = 1, j = 4
> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
> > i
> > > = 2, j = 4
> > > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11
> > , i
> > > = 3 , j = 4
> > > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 ,
> > i
> > > = 4 , j = 4
>
> > > out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> > > So basically among this we have to find element closest X ( where
> > element <
> > > = X )
> > > hence 12 is the answer.
>
> > > On Thu, Dec 1, 2011 at 3:11 PM, atul anand
> > wrote:
> > > > @sourabh
>
> > > > i guess you need to modify this statement :-
>
> > > > 3) Now for each element B[i][0] , do a (modified) binary *search for
> > > > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > > > +1... n][0] ,
> > > > Say the found index after binary search is j ( which is > i)...
>
> > > > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,
> > i
> > > > = 1, j = 3
> > > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
> > i =
> > > > 2, j = 4
> > > > 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> > > > *Cumulative SUM*
>
> > > > *i*
>
> > > > 2
>
> > > > 0
>
> > > > 3
>
> > > > 1
>
> > > > 6
>
> > > > 2
>
> > > > 10
>
> > > > 3
>
> > > > *15*
>
> > > > 4
>
> > > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > > > ..right ??
>
> > --
> > 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.
Re: [algogeeks] Re: Sub-array problem
yup i made some calculation error
Now this algo works perfectly :) :)
Thanks for your help and explanation :) :)
On Thu, Dec 1, 2011 at 4:26 PM, sourabh wrote:
> @atul ...
>
> Reply 1:
> Yes, you are correct.. i missed it... Correct statement is as follows:
>
> 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
> i = 3, j = 4
> 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
> =5 , i = 4, j = 4
>
> -
>
> Reply 2:
> I might be wrong in calculating 12 + 2 = 14 but i guess you are
> not getting my point even if 14 is the search element, still the
> element smaller than equal to 14 in array B is 10 and not 15...
>
> Hence, the above calculation that you have made are incorrect.
>
> If you look at the problem statement it says that we have to find the
> sum which is smaller than equal to X.
> Now, if you look ta ur calculations you will see that your 'closest to
> X' search space contains elements 13 which is invalid as it is greater
> than 12...
>
> Hence, i m re-calculating the values based on the above given
> algorithm...
>
> 12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
> 8 , i = 1, j = 3
>
> 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
> =12 , i = 2, j = 4
>
> 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
> 9 , i = 3 , j = 4
>
> 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
> 5 , i = 4 , j = 4
>
> Also, as calculated in the previous post the corner case gives 10 as
> the closest to X.
>
> Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
> 12.
>
> On Dec 1, 2:52 pm, atul anand wrote:
> > and you made mistake above in calculating 12 + 2 = *12* , its 14
> >
> > 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 ,
> i
> > = 1, j = 4
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
> i
> > = 2, j = 4
> > 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11
> , i
> > = 3 , j = 4
> > 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 ,
> i
> > = 4 , j = 4
> >
> > out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> > So basically among this we have to find element closest X ( where
> element <
> > = X )
> > hence 12 is the answer.
> >
> >
> >
> >
> >
> >
> >
> > On Thu, Dec 1, 2011 at 3:11 PM, atul anand
> wrote:
> > > @sourabh
> >
> > > i guess you need to modify this statement :-
> >
> > > 3) Now for each element B[i][0] , do a (modified) binary *search for
> > > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > > +1... n][0] ,
> > > Say the found index after binary search is j ( which is > i)...
> >
> > > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 ,
> i
> > > = 1, j = 3
> > > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 ,
> i =
> > > 2, j = 4
> > > 12 + 6 = 18 , closest element found = *no element found ??? how *
> >
> > > *Cumulative SUM*
> >
> > > *i*
> >
> > > 2
> >
> > > 0
> >
> > > 3
> >
> > > 1
> >
> > > 6
> >
> > > 2
> >
> > > 10
> >
> > > 3
> >
> > > *15*
> >
> > > 4
> >
> > > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > > ..right ??
>
> --
> 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.
[algogeeks] Re: Sub-array problem
@atul ...
Reply 1:
Yes, you are correct.. i missed it... Correct statement is as follows:
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =9 ,
i = 3, j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10
=5 , i = 4, j = 4
-
Reply 2:
I might be wrong in calculating 12 + 2 = 14 but i guess you are
not getting my point even if 14 is the search element, still the
element smaller than equal to 14 in array B is 10 and not 15...
Hence, the above calculation that you have made are incorrect.
If you look at the problem statement it says that we have to find the
sum which is smaller than equal to X.
Now, if you look ta ur calculations you will see that your 'closest to
X' search space contains elements 13 which is invalid as it is greater
than 12...
Hence, i m re-calculating the values based on the above given
algorithm...
12 + 2 = 14, closest element found = 10 , closest to X = 10 - 2 =
8 , i = 1, j = 3
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3
=12 , i = 2, j = 4
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 =
9 , i = 3 , j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 =
5 , i = 4 , j = 4
Also, as calculated in the previous post the corner case gives 10 as
the closest to X.
Hence, max of all closest values to X = max { 8, 12, 9, 5, 10 } =
12.
On Dec 1, 2:52 pm, atul anand wrote:
> and you made mistake above in calculating 12 + 2 = *12* , its 14
>
> 12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 , i
> = 1, j = 4
> 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i
> = 2, j = 4
> 12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11 , i
> = 3 , j = 4
> 12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 , i
> = 4 , j = 4
>
> out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
> So basically among this we have to find element closest X ( where element <
> = X )
> hence 12 is the answer.
>
>
>
>
>
>
>
> On Thu, Dec 1, 2011 at 3:11 PM, atul anand wrote:
> > @sourabh
>
> > i guess you need to modify this statement :-
>
> > 3) Now for each element B[i][0] , do a (modified) binary *search for
> > the closest value smaller than equal to (X + B[i][0])* in array B[i
> > +1... n][0] ,
> > Say the found index after binary search is j ( which is > i)...
>
> > 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 , i
> > = 1, j = 3
> > 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i =
> > 2, j = 4
> > 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> > *Cumulative SUM*
>
> > *i*
>
> > 2
>
> > 0
>
> > 3
>
> > 1
>
> > 6
>
> > 2
>
> > 10
>
> > 3
>
> > *15*
>
> > 4
>
> > for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> > ..right ??
--
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.
Re: [algogeeks] Link list Q
Option (c) is correct. detects the loop in singly linked list
**
On Thu, Dec 1, 2011 at 1:42 PM, Vijay Khandar wrote:
> What does the following program do on the singly linked list?
>
> p=head;
> q=head->next;
> while(p!=null && q!null)
> {
> if(p==q)
> {
> exit(0)
> }
> p=p->next;
> q=(q->next)?(q->next->next):q->next;
> }
>
> a)traverse the entire singly linked list
> b)detects the duplicate nodes
> c)detects the loop in singly linked list
> d)detects the duplicate nodes at alternate places
>
> plz explain anyone with correct option..
>
> --
> 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.
Re: [algogeeks] Re: Sub-array problem
and you made mistake above in calculating 12 + 2 = *12* , its 14
12 + 2 = 14, closest element found = 15 , closest to X = 15 - 2 = 13 , i
= 1, j = 4
12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i
= 2, j = 4
12 + 6 = 18 , closest element found = 15 , closest to X = 15 - 6 = 11 , i
= 3 , j = 4
12 + 10 = 22 , closest element found = 15 , closest to X = 15 - 10 = 5 , i
= 4 , j = 4
out of {10,13,12,11,5 } , element 12 is closest to X ( which is 12) .
So basically among this we have to find element closest X ( where element <
= X )
hence 12 is the answer.
On Thu, Dec 1, 2011 at 3:11 PM, atul anand wrote:
> @sourabh
>
> i guess you need to modify this statement :-
>
> 3) Now for each element B[i][0] , do a (modified) binary *search for
> the closest value smaller than equal to (X + B[i][0])* in array B[i
> +1... n][0] ,
> Say the found index after binary search is j ( which is > i)...
>
> 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 , i
> = 1, j = 3
> 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i =
> 2, j = 4
> 12 + 6 = 18 , closest element found = *no element found ??? how *
>
> *Cumulative SUM*
>
> *i*
>
> 2
>
> 0
>
> 3
>
> 1
>
> 6
>
> 2
>
> 10
>
> 3
>
> *15*
>
> 4
>
> for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 )
> ..right ??
>
>
>
>
>
--
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.
Re: [algogeeks] Re: Sub-array problem
@sourabh i guess you need to modify this statement :- 3) Now for each element B[i][0] , do a (modified) binary *search for the closest value smaller than equal to (X + B[i][0])* in array B[i +1... n][0] , Say the found index after binary search is j ( which is > i)... 12 + 2 = 12 , closest element found = 10 , closest to X = 10 - 2 = 8 , i = 1, j = 3 12 + 3 = 15 , closest element found = 15 , closest to X = 15 - 3 =12 , i = 2, j = 4 12 + 6 = 18 , closest element found = *no element found ??? how * *Cumulative SUM* *i* 2 0 3 1 6 2 10 3 *15* 4 for 12 + 6 =18 , closest element less than equal to 18 = 15 (15 < 18 ) ..right ?? -- 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.
Re: [algogeeks] Link list Q
detects the loop in singly linked list
On Thu, Dec 1, 2011 at 2:41 PM, rahul vatsa wrote:
> detects the loop in singly linked list.
>
>
>
> On Thu, Dec 1, 2011 at 1:42 PM, Vijay Khandar wrote:
>
>> What does the following program do on the singly linked list?
>>
>> p=head;
>> q=head->next;
>> while(p!=null && q!null)
>> {
>> if(p==q)
>> {
>> exit(0)
>> }
>> p=p->next;
>> q=(q->next)?(q->next->next):q->next;
>> }
>>
>> a)traverse the entire singly linked list
>> b)detects the duplicate nodes
>> c)detects the loop in singly linked list
>> d)detects the duplicate nodes at alternate places
>>
>> plz explain anyone with correct option..
>>
>> --
>> 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.
>
--
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.
Re: [algogeeks] Link list Q
detects the loop in singly linked list.
On Thu, Dec 1, 2011 at 1:42 PM, Vijay Khandar wrote:
> What does the following program do on the singly linked list?
>
> p=head;
> q=head->next;
> while(p!=null && q!null)
> {
> if(p==q)
> {
> exit(0)
> }
> p=p->next;
> q=(q->next)?(q->next->next):q->next;
> }
>
> a)traverse the entire singly linked list
> b)detects the duplicate nodes
> c)detects the loop in singly linked list
> d)detects the duplicate nodes at alternate places
>
> plz explain anyone with correct option..
>
> --
> 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.
[algogeeks] Link list Q
What does the following program do on the singly linked list?
p=head;
q=head->next;
while(p!=null && q!null)
{
if(p==q)
{
exit(0)
}
p=p->next;
q=(q->next)?(q->next->next):q->next;
}
a)traverse the entire singly linked list
b)detects the duplicate nodes
c)detects the loop in singly linked list
d)detects the duplicate nodes at alternate places
plz explain anyone with correct option..
--
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.
