Re: [algogeeks] Finding all prime less than 10^8
thankx for u r reply.in my code i implemented Sieve of Eratosthenesthat
but some type of optimization were required that i have done...got accepted.
On Wed, Apr 14, 2010 at 2:57 PM, Ashish Mishra amishra@gmail.comwrote:
The Sieve of Eratosthenes is best for finding prime
On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD patidarc...@gmail.comwrote:
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy
karthik.gin...@gmail.comwrote:
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff
logic..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ashish Mishra
http://ashishmishra.weebly.com/
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
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.
My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy karthik.gin...@gmail.comwrote:
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff
logic..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
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.
My+Sign.JPG
Re: [algogeeks] efficient backtracking algorithm for the coin changing problem
this is dynamic programming problem. try to use dynamic programming... On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- BL/\CK_D!AMOND -- 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] efficient backtracking algorithm for the coin changing problem
here is simple way to do it..: A[1000] //1000 is maximum formadable sum can be provided.. S is set of coins that you have,K is the sum to be formed initialize the array A by larege value for(x in S): A[x]=1 for 0i1000 for 0j1000 if(i+j1000 A[i]+A[j]A[i+j] ) A[i+j]=A[i]+A[j] return A[K] On Sat, Apr 10, 2010 at 6:27 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: What do u mean by y u need backtracking DP needs backtracking to reconstruct the solution. -Rohit On Sat, Apr 10, 2010 at 3:27 PM, Ashish Mishra amishra@gmail.com wrote: y u need backtracking i think it can be done with DP On Sat, Apr 10, 2010 at 9:12 AM, «« ÄÑÜJ »» anujlove...@gmail.com wrote: Need help in designing efficient backtracking algorithm for the coin changing problem. where a1, a2, an are the set of distinct coins types, where each ai is an integer. and each type is unlimited quantity. the problem to make up the exact amount C using minimum total number of coins. use backtracking template with a bounding function.. help appreciated.. -- 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. -- How soon 'not now' becomes 'never'... -- 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. -- BL/\CK_D!AMOND -- 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]
is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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]
ok...sorry u asked the data structure.. On Wed, Mar 31, 2010 at 11:54 AM, BlackdiamonD patidarc...@gmail.comwrote: is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.comwrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- BL/\CK_D!AMOND -- 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] Implementation of Algorithms
you can go through this.: http://www.topcoder.com/tc?d1=tutorialsd2=alg_indexmodule=Static and you can follow: Art of Uva online judge for getting started in this contest... On Wed, Mar 31, 2010 at 12:05 AM, scanfile rahul08k...@gmail.com wrote: I am new to the world of programming. I have to solve the problems on the spoj.pl , but I have no idea that how I would implement the algorithms in any programming language. Pls help me. I need a solution of this problem. Thanx scanfile -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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]
what if your sort the element.first time.. applying binary search on list for x1 (getting minimum index ) applying binary search on list for x2(getting maximum index) element between this index will be the answer. complexity:O(log(N)) for getting the range. (not considering the sorting) On Wed, Mar 31, 2010 at 11:55 AM, BlackdiamonD patidarc...@gmail.comwrote: ok...sorry u asked the data structure.. On Wed, Mar 31, 2010 at 11:54 AM, BlackdiamonD patidarc...@gmail.comwrote: is the list is sorted...or in some order... i feel unless the point in the list in some order eg: sorted, it will be difficult to get soluiton less than O(n) On Wed, Mar 31, 2010 at 4:59 AM, Priyanka Chatterjee dona.1...@gmail.com wrote: Design an efficient algorithm to report all the points within x1 and x2 from a list of N integers. What data structure will you use to implement this algorithm? Find the order of complexity . ( An O(N) solution is not asked) -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- BL/\CK_D!AMOND -- BL/\CK_D!AMOND -- 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] Implementation of Algorithms
ok i previously i written wrong it is :*Art-of-Programming*-Contest-SE-for- *Uva book for basic of programming and some of the solving methods for problems. here is the Link Art_of_Programming_Contest_SE_for_uva.pdfhttp://online-judge.uva.es/p/Art_of_Programming_Contest_SE_for_uva.pdf * On Wed, Mar 31, 2010 at 5:42 PM, naga vinod kumar vinodkumark...@gmail.comwrote: Hii, what is Art of Uva online judge Does it contain some training material like USACO -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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]
*Binary Indexed Trees* or *Segment Interval trees*. building them also it will take O(n log(n)) ..i feel for a particular query it will be difficult less than O(n) .because .u must know all the element. On Wed, Mar 31, 2010 at 8:26 PM, Priyanka Chatterjee dona.1...@gmail.comwrote: The list of N integers is not sorted. The solution is asked for a particular query. @Abhijit Reddy: Can you elaborate more on* Binary Indexed Trees* or *Segment Interval trees*. May be you opted for the correct data structure. Please give the algorithm. @All: Doing a sorting for O(n logn) and then binary search for x1 and x2 in O(logn) will be less efficient than the simple solution of O(n). Think on the data structure that can optimize it. Is it possible in time complexity O(n)? -- Thanks Regards, Priyanka Chatterjee Third Year Undergraduate Student, Computer Science Engineering, National Institute Of Technology,Durgapur India http://priyanka-nit.blogspot.com/ -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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] First k smallest elements
nice solution appreciate it. but your algorithm is wasting time in finding all the element... instead of that just find boundary line kth element which can help as in finding element greater that kth and element small than kth and that soluton can be done in O(N) On Sun, Mar 28, 2010 at 10:02 PM, CHERUVU JAANU REDDY jaanu.cher...@gmail.com wrote: 1) Construct max heap by taking first k elements in an array 2) if k+1 element less than root of max heap a) Delete root of max heap b) Insert k+1 element in max heap and apply heapify method 3) else skip the element 4) apply above procedure for all n elements in an array At last you will get k smallest elements and root is kth smallest element in the array this is O(nlogk) CHERUVU JAANU REDDY M.Tech in CSIS On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.comwrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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. 338.gif361.gif
Re: [algogeeks] Finding the middle of the linked list which has also cycle in the list
vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.comwrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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] Finding the middle of the linked list which has also cycle in the list
in starting we keep track of head pointer.. we are having three pointers head,slower,faster, know we start traversing the list if(faster==head||faster-next==head) return slower else faster=faster-next-next slower=slower-next On Sun, Mar 28, 2010 at 12:15 PM, vikrant singh vikrantsing...@gmail.comwrote: @diamond sorry but how do we know the fast pointer is pointing to head again? u see, in case u dont have O(n) space to record visited nodes On Sun, Mar 28, 2010 at 10:28 AM, blackDiamond patidarc...@gmail.comwrote: vikrant you havent read properly the post by Gaurav when the second pointer will come back to the head first will be pointing the middle.(Think it)!! On Sun, Mar 28, 2010 at 10:21 AM, vikrant singh vikrantsing...@gmail.com wrote: Well gaurav, i think by this method you can only check for a cycle in the list. If u have any idea how can you implement this to solve originally posted problem? On Sat, Mar 27, 2010 at 9:03 AM, gaurav kishan gauravkis...@gmail.comwrote: Hi, Keep two pointers both initially pointing to Head. Move first pointer one by one and the second pointer by two nodes in each iteration. When second pointer next link points to head again,return first pointer. Please let me know if this can be further imporved upon or there is some fallacy in the approach. Regards, Gaurav. -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Vikrant Singh -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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] First k smallest elements
you have to find the kth element of your list. which will take O(n) and remaining element you can get in the other traversal eg: 3,5,4,35,599,34 you have to find the 3 min element from the lsit so finding 3rd element we will get 5 on next thing is traverse the list and take all the element less than 5, eg:3,5,4 is this clear your doubt ...? or i have gone on the other way... On Sun, Mar 28, 2010 at 8:41 PM, abhijith reddy abhijith200...@gmail.comwrote: Can any one tell how to do this when there are 'm' queries like query i j k find the kth largest element in between indices i-j in an array. When m is large even an O(n) algorithm would be slow. I thinking that each query could be answered in O(sqrt(n)) time So any suggestions ? Thanks On Sun, Mar 28, 2010 at 7:57 PM, blackDiamond patidarc...@gmail.comwrote: there are better solution of O(n) are posted in the thread...[?]. using order statices On Sun, Mar 28, 2010 at 6:49 PM, Mukesh Kumar thakur mukeshraj8...@gmail.com wrote: Create a temp array temp[0..k-1] of size k. 2) Traverse the array arr[k..n-1]. While traversing, keep updating the smallest element of temp[] 3) Return the smallest of temp[] Time Complexity: O((n-k)*k). try it ..for this problem[?] -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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. 338.gif361.gif
Re: [algogeeks] basic problem
struct are passed by value..not by reference... On Wed, Mar 24, 2010 at 2:42 AM, aman goyal aman...@gmail.com wrote: why do we use malloc funtcn to allocate memory for a stuct node variable pointer.. why dont we simply write struct node p; instead we do struct node *p p=malloc(); any valid reasons for this?? -- 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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- 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.
