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;
> whil
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 tha
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@
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
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 emai
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 discuss
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
wo
@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 step
@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"
> #inclu
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;
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
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 mo
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
@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 eleme
@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
--
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
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
@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 elem
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;
>> wh
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;
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)d
22 matches
Mail list logo