[algogeeks] standard puzzle
There are 10 coins in a bag. 3 coin weights x kg 3 coins weights y kg 2 coins weights z kg 2 coins weights w kg You have to separate them into separate heaps according to their weights. -- 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: MS Question : find word in 2D array
This can be done with a dfs to mark the path and a backtrack to construct the path or the word itself. -- 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] [amazon]: dutch national flag algorithm
it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.comwrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- 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/-/54GHWSwHHw8J. 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. -- Cheers, Nishant Pandey |Specialist Tools Development | npan...@google.comgvib...@google.com | +91-9911258345 -- 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] standard puzzle
question is incomplete , mention the conditions please On Sun, Jun 10, 2012 at 11:44 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: There are 10 coins in a bag. 3 coin weights x kg 3 coins weights y kg 2 coins weights z kg 2 coins weights w kg You have to separate them into separate heaps according to their weights. -- 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. -- Thanks Regards Saurabh Yadav -- 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] standard puzzle
u have to separate them into 4 heaps in min number of comparisons . given a weighing balance On Sun, Jun 10, 2012 at 12:05 PM, Saurabh Yadav saurabh...@gmail.comwrote: question is incomplete , mention the conditions please On Sun, Jun 10, 2012 at 11:44 AM, HARSHIT PAHUJA hpahuja.mn...@gmail.comwrote: There are 10 coins in a bag. 3 coin weights x kg 3 coins weights y kg 2 coins weights z kg 2 coins weights w kg You have to separate them into separate heaps according to their weights. -- 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. -- Thanks Regards Saurabh Yadav -- 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. -- HARSHIT PAHUJA M.N.N.I.T. ALLAHABAD -- 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] [amazon]: dutch national flag algorithm
Just use the counting sort and keep the counts in variables int R, int G, int B. Traverse the array and increment each respective variable (R or G or B) as soon as you encounter upon it. Once finished, you will have all the counts of frequencies stored in those three variables. Now, start traversing the array of counts (R, G, B) and fill the original array with data. Space O(1), time O(N) Rgds, Ashot Madatyan From: algogeeks@googlegroups.com [mailto:algogeeks@googlegroups.com] On Behalf Of Nishant Pandey Sent: Saturday, June 09, 2012 10:16 PM To: algogeeks@googlegroups.com Subject: Re: [algogeeks] [amazon]: dutch national flag algorithm it can be solved in o(n) , keep one pointer at start and another pointer at the last , traverse the string if u get R swap it at the start position and then increament it , if u get B swap it with last pointer pointing to last position .and then decrement it . in this way all things will come in place . On Sat, Jun 9, 2012 at 11:36 PM, Navin Kumar algorithm.i...@gmail.com wrote: Given a character array as input. Array contains only three types of characters 'R', 'G' and 'B'. Sort the array such that all 'R's comes before 'G's and all 'G's comes before 'B's. Constraint :- No extra space allowed(except O(1) space like variables) and minimize the time complexity. You can only traverse the array once. -- 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/-/54GHWSwHHw8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com mailto:algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Cheers, Nishant Pandey | Specialist Tools Development | npandey mailto:gvib...@google.com @google.com | +91-9911258345 -- 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] complex notation
printf(%d\n, (int) ((int*)0 +1)); its prints no. of bytes in integer. please explain what does this mean? what and how is happening in this? -- Regards Anika Jain -- 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] complex notation
0 will be typecasted into int pointer giving 0th memory location and then adding 1 to that location will be 4 (moving to the next immediate address of integer pointer coz size of integer pointer is 4 byte on 32 bit machines) according to integer pointer arithmatic. so when memory location is again typecasted into int giving integer value of that location. If u were using 64 bit system answer would be 8. On Sun, Jun 10, 2012 at 2:23 PM, Anika Jain anika.jai...@gmail.com wrote: printf(%d\n, (int) ((int*)0 +1)); its prints no. of bytes in integer. please explain what does this mean? what and how is happening in this? -- Regards Anika Jain -- 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] complex notation
in above post, memory location implies value stored in that location and not the value of actual memory location :-) On Sun, Jun 10, 2012 at 2:23 PM, Anika Jain anika.jai...@gmail.com wrote: printf(%d\n, (int) ((int*)0 +1)); its prints no. of bytes in integer. please explain what does this mean? what and how is happening in this? -- Regards Anika Jain -- 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] problem
Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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] [amazon]: dutch national flag algorithm
int low,mid,high; low = mid = 0; high = (int)(sizeof(arr)/sizeof(arr[0]))-1; /* According to Dutch national flag problem there are three types of quantities in an array and we have to combine these elements together but in a certain order Let the elements in the array are in the form 0,1,2 then these elements in an array should appear in order 0 then 1 then 2 ( low to middle-1 ) - elements having 0 as a number (middle to high-1 ) - 1 as a number ( high to arr - size) - 2 as a number / n = high; for ( int i = 0; i = n; i++ ) { if ( arr[mid] == 0 ) { swap(arr[low],arr[mid]); low++; mid++; } else if ( arr[mid] == 2 ) { swap(arr[mid],arr[high]); high--; } else { mid++; } } -- 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: problem
what are the constraints or limits for a,b and n?? On Jun 10, 3:07 pm, payel roy smithpa...@gmail.com wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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] [amazon]: dutch national flag algorithm
@Ashot: You can traverse array one time. In your case you are traversing twice. First for counting occurrence of R , G and B then again traversing for assigning values. But constraints is that you have to traverse only once. On Sun, Jun 10, 2012 at 5:13 PM, Akshat Sapra sapraaks...@gmail.com wrote: int low,mid,high; low = mid = 0; high = (int)(sizeof(arr)/sizeof(arr[0]))-1; /* According to Dutch national flag problem there are three types of quantities in an array and we have to combine these elements together but in a certain order Let the elements in the array are in the form 0,1,2 then these elements in an array should appear in order 0 then 1 then 2 ( low to middle-1 ) - elements having 0 as a number (middle to high-1 ) - 1 as a number ( high to arr - size) - 2 as a number / n = high; for ( int i = 0; i = n; i++ ) { if ( arr[mid] == 0 ) { swap(arr[low],arr[mid]); low++; mid++; } else if ( arr[mid] == 2 ) { swap(arr[mid],arr[high]); high--; } else { mid++; } } -- 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: problem
No constraints as such! On 10 June 2012 17:19, Nachammai Lakshmanan nnlna...@gmail.com wrote: what are the constraints or limits for a,b and n?? On Jun 10, 3:07 pm, payel roy smithpa...@gmail.com wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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: problem
This problem is of ACM-ICPC kanpur online round 2012. you can find the solution herehttp://www.codechef.com/ACMKAN11/problems/ARTHMNCY . On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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/-/0tnSKnC7YRYJ. 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] [amazon]: dutch national flag algorithm
sorry for the above post , there was careless mistake of mine. The code will be [code] int low,mid,high; low = mid = 0; high = (int)(sizeof(arr)/sizeof(arr[0]))-1; /* According to Dutch national flag problem there are three types of quantities in an array and we have to combine these elements together but in a certain order Let the elements in the array are in the form 0,1,2 then these elements in an array should appear in order 0 then 1 then 2 ( low to middle-1 ) - elements having 0 as a number (middle to high-1 ) - 1 as a number ( high to arr - size) - 2 as a number / n = high; while ( mid = high ) { if ( arr[mid] == 0 ) { swap(arr[low],arr[mid]); low++; mid++; } else if ( arr[mid] == 2 ) { swap(arr[mid],arr[high]); high--; } else { mid++; } } [/code] -- 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: problem
Can you please simplify the algorithm? Solution is not clear from the posted submissions !!! On 10 June 2012 20:32, KK kunalkapadi...@gmail.com wrote: This problem is of ACM-ICPC kanpur online round 2012. you can find the solution herehttp://www.codechef.com/ACMKAN11/problems/ARTHMNCY . On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. *gcd(a, b) = 1* 2. *0 a/b 1* 3. *a * b = (n!) ^ (n!)* Where *n!* denotes the factorial of n and ^ denotes power, *i.e. (2!) ^ (2!) = 4*. -- 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/-/0tnSKnC7YRYJ. 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] Amazon : Find popular cost
Here, we can use hashmap and use an extra variable max_till_now that will keep track of maximum element occured to us till now while updating. Time complexity of solution will be O(n) max_till_now = 0; for ( int i = 0; i arr.size(); i++ ) { hashmap[arr[i]] += 1; if ( hashmap[arr[i]] max_till_now ) max_till_now = hashmap[arr[i]]; } print(max_till_now); -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.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] Re: problem
A correction, it is *(2^p) - 1 *, and the answer (*2^(number of primes less than n)) - 1* .(It is simply taking any subset of the primes,leaving the one in which do not take any prime) On Sun, Jun 10, 2012 at 10:03 PM, Piyush Kapoor pkjee2...@gmail.com wrote: The problem simply asks you to calculate the number of ways to express a number( = *N!^N!*) as product of two co prime numbers. For a general *N* , it is simply equal to *2^(p-1)* , where *p * is the number of distinct prime factors of *N*. For *N!* , *p* will be number of primes less than *N* , and for *N!^N!* it is same as *N!* , So the answer is *2^((number of primes less than N) - 1)* . On Sun, Jun 10, 2012 at 9:53 PM, payel roy smithpa...@gmail.com wrote: Can you please simplify the algorithm? Solution is not clear from the posted submissions !!! On 10 June 2012 20:32, KK kunalkapadi...@gmail.com wrote: This problem is of ACM-ICPC kanpur online round 2012. you can find the solution here. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. gcd(a, b) = 1 2. 0 a/b 1 3. a * b = (n!) ^ (n!) Where n! denotes the factorial of n and ^ denotes power, i.e. (2!) ^ (2!) = 4. On Sunday, 10 June 2012 16:37:33 UTC+5:30, payel roy wrote: Find the number of fractions a/b such that- 1. gcd(a, b) = 1 2. 0 a/b 1 3. a * b = (n!) ^ (n!) Where n! denotes the factorial of n and ^ denotes power, i.e. (2!) ^ (2!) = 4. -- 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/-/0tnSKnC7YRYJ. 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. -- Regards, Piyush Kapoor, 2nd year,CSE IT-BHU -- *Regards,* *Piyush Kapoor,* *2nd year,CSE IT-BHU* -- 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.