Re: [algogeeks] 4Sum
@KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.com wrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/9jCCN5iHDB8J. 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, Jalaj Jaiswal Software Engineer, Zynga Inc +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89 LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro -- 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]
@ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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]
@ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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]
rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.comwrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- Umer -- 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]
@Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.com wrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.comwrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- Umer -- 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]
@ *ALL* please. post along with your method . proof than it make's equal distribution over the given range. On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.com wrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.com wrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- Umer -- 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.
[algogeeks] LCA tutorial
I was going through this tutorial http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor but i was not able to fully understand the O(N), O(1) algorithm for the restricted RMQ. They have converted the array into a new binary array and find a solution for this new array. But how they are getting the solution for the original array? -- 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/-/4Za8aJYhwEUJ. 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]
@Umer and Navin : 1 is generated by (1,3) only. 2 is generated by (1,1) and (2,3). so given solution is wrong On Tue, Jun 19, 2012 at 5:17 AM, Sourabh Singh singhsourab...@gmail.comwrote: @ *ALL* please. post along with your method . proof than it make's equal distribution over the given range. On Tue, Jun 19, 2012 at 4:47 AM, Navin Kumar algorithm.i...@gmail.comwrote: @Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.com wrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.com wrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- Umer -- 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]
Thanks for bringing that up, Navin. Anyway, by this approach the prob of getting 3,4,5 will be greater than getting 1,2 or 6,7 Another workaround can be. ran - rand(5) if (ran == 1) return 6; else if (ran == 2) return 7; else return (rand(5)); On Tue, Jun 19, 2012 at 4:47 PM, Navin Kumar algorithm.i...@gmail.comwrote: @Umer: rand(5) + (rand(5)%2): = it will never give 6 because for rand(7) range will be 0-6. So better try this: rand(5) + (rand(5)%3). On Tue, Jun 19, 2012 at 2:45 PM, Umer Farooq the.um...@gmail.com wrote: rand(5) + (rand(5)%2); On Tue, Jun 19, 2012 at 12:30 PM, Sourabh Singh singhsourab...@gmail.com wrote: @ sry condition should be: if(20*prob = 500/7) :-) On Tue, Jun 19, 2012 at 12:26 AM, Sourabh Singh singhsourab...@gmail.com wrote: @ALL Given a random number generator say r(5) generates number between 1-5 uniformly at random , use it to in r(7) which should generate a random number between 1-7 uniformly at random i have seen this on many site's but not a single correct solution. all solution's posted got rejected by someone else.: plz.. suggest some algo : my aprroach: let's assume a rectangle : 100 |___ |___|__ 500/7 | || | || |___|__| 0 1 2 3 4 5 67 now : let : num = rand(5); prob = rand(5); if(prob = rand(5)) print num else print 5 + num*(2/5) -- 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. -- Umer -- 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. -- Umer -- 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: Directi question-centre of the tree
for getting diameter we can simply add the max height of left subtree and max height of the right sub tree . the main issue is how efficiently we find median on that longest path to get the center of the tree . can any bdy sugest optimized algo for that ? On Mon, Jun 18, 2012 at 6:08 PM, rajesh pandey rajesh.pandey.i...@gmail.com wrote: I found it in some paper ;) Diameter and center De nition 4. The diameter of tree is the length of the longest path. De nition 5. A center is a vertex v such that the longest path from v to a leaf is minimal over all vertices in the tree.Tree center(s) can be found using simple algorithm. Algorithm 1. (Centers of tree) 1: Choose a random root r. 2: Find a vertex v1 | the farthest form r. 3: Find a vertex v2 | the farthest form v1. 4: Diameter is a length of path from v1 to v2. 5: Center is a median element(s) of path from v1 to v2. This is O(n) algorithm. It is clear that we can't determine tree isomorphism faster than O(n). So, if we nd a O(f(n)) algorithm for rooted trees isomorphism we can also obtain O(f(n)) algorithm for ordinary trees. On Saturday, June 16, 2012 12:04:32 PM UTC+5:30, achala sharma wrote: I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.in -- 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/-/HnMOZtOrkqwJhttps://groups.google.com/d/msg/algogeeks/-/HnMOZtOrkqwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- Hemesh singh -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en. -- 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/-/BWplK7bCatMJ. 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.
[algogeeks] Coin On The Table
Please suggest how to go about solving the following question... https://www.interviewstreet.com/challenges/dashboard/#problem/4fb12fb9cb75b -- 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] POSTAGE STAMP PROBLEM
The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the letter can hold only a limited number of stamps, and these may only have certain specified face values. For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps. Is there an algorithm that given the maximum amount of stamps allowed and the face value of the stamps, one can find the smallest postage that cannot be placed on the envelope? -- 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] Coin On The Table
check this discussion http://stackoverflow.com/questions/3826975/algorithm-for-postage-stamp-problem goog_1170506352-- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 9:19 PM, g4ur4v gauravyadav1...@gmail.com wrote: Please suggest how to go about solving the following question... https://www.interviewstreet.com/challenges/dashboard/#problem/4fb12fb9cb75b -- 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: POSTAGE STAMP PROBLEM
This can be done with DP.
Take an array with values 1 to n.
For every number i, try to make it using the stamps available and the 1 to
i-1 array. Anytime u find that the upper bound is reached, u return.
sudo code.
stamps[K]; - Stamp denominations available.
a[N] - Array of number of stamps required.
a[0] = 0;
For i= 1 to n
{
tempMin = 1000( some large number)
For j = 0 to K - loop over the array storing the number of stamp
denominations.
{
if(stamps[j] = i)
if( tempMin 1 + a[i-j])
tempMin := 1 + a[i-j];
}
if(tempMin maxStampAllowed)
{
return i;
}
else
{
a[i] =tempMin
}
}
This will work with time complexity of O (n*k) . Use of vectors (in c++)
can be helpfule for dynamic arrays.
P.S. Can we do better?
On Tuesday, June 19, 2012 9:25:42 PM UTC+5:30, suzi wrote:
The postage stamp problem is a mathematical riddle that asks what is the
smallest postage value which cannot be placed on an envelope, if the letter
can hold only a limited number of stamps, and these may only have certain
specified face values.
For example, suppose the envelope can hold only three stamps, and the
available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the
solution is 13 cents; since any smaller value can be obtained with at most
three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one
must use at least four stamps.
Is there an algorithm that given the maximum amount of stamps allowed and
the face value of the stamps, one can find the smallest postage that cannot
be placed on the envelope?
--
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/-/a1ykZ8HaDjEJ.
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] Deterministic Selection Algorithm
Hi all, I've been trying to implement http://www.ics.uci.edu/~eppstein/161/960130.html the explained algorithm. I have implemented it also, but I don't know why it sometimes gives incorrect answer. I also looked to the already implemented version available on net https://www.rsndev.com/blog/22 But it also gave wrong answer for some cases, increase the value of 'q' in that. I was wondering if anyone of you have implemented it in C, could you share your code. Thanks. -- 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] 4Sum
@Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en . -- 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/-/9jCCN5iHDB8J. 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, Jalaj Jaiswal Software Engineer, Zynga Inc +91-9019947895 * * FACEBOOK http://www.facebook.com/jalaj.jaiswal89 LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro -- 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/-/SGN_A_YrZlkJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email
Re: [algogeeks] 4Sum
@rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@* *googlegr**oups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- 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/-/9jCCN5iHDB8Jhttps://groups.google.com/d/msg/algogeeks/-/9jCCN5iHDB8J . To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group/algogeeks?hl=en 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+unsubscribe@** googlegroups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this
Re: [algogeeks] Re: Microsoft question
This can be done using the concept of median of medians, wherein we can achieve linear time complexity in the worst case. This is a concept used in parallel algorithms too, check it out. On Mon, Jun 18, 2012 at 5:38 PM, Prem Nagarajan prem.cmna...@gmail.comwrote: @enchantress : This problem can be solved using quicksort in O(nlogn). No need to go for selection sort. But O(n) solution is needed. On Mon, Jun 18, 2012 at 2:50 PM, enchantress elaenjoy...@gmail.comwrote: Hi all, A variation of selection sort can be used which takes O(nk) time. for i 1 to k min_index = i for j i+1 to n if a[j] a[min_index] min_index = j swap(a[i],a[min_index]) required element : a[k] On Sunday, 17 June 2012 08:13:18 UTC+5:30, Prem Nagarajan wrote: Give an array of unsorted elements, find the kth smallest element in the array. The expected time complexity is O(n) and no extra memory space should be used. Quickselect algorithm can be used to obtain the solution. Can anyone explain how quickselect works? -- 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/-/FABBRabzVqMJ. 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] 4Sum
Lets see ur example... We can have two other arrays corresponding to our n^2 array. For every (target-arr[i]) which we search in our look up array, we can also search the components which were used to get that sum. This can be done in addition constant amount search. I hope we can still go with Hemesh's algo. Please let me know if it breaks somewhere... let's take a test case : arr: 2 4 68 arr[0]: 6 8 10 10 12 14 arr[1]: 2 22 4 46 arr[2]: 4 68 6 88 P.S. Can we do better? On Wednesday, June 20, 2012 12:22:52 AM UTC+5:30, Amol Sharma wrote: @rammar: can you please explain the case...which i took in the earlier post..with this method. -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Tue, Jun 19, 2012 at 11:27 PM, rammar getam...@gmail.com wrote: @Hemesh +1 Please correct me if i am wrong. Creation of our look up array a[n*n] - sum of all the pairs will take O(n^2). Search using binary sort or quick sort in O(n^2 log (n^2) ) == O(n^2 log n) We will traverse this array, and for every element we will find (target - a[i]) - This traversal will again take O(n^2). For every (target -a[i]) we will search it in our lookup array using binary search - This will take O(log n^2) = O(2log n) = O(log n) We will store all the matched for the target. Final complexity = O(n^2) + O(n^2 log n) + O(n^2)*O(log n) == O (n^2 log n) If the values of max of a[n] is not very high, we can go with a hash map. This will result in a quick look up. And we can get the answer in O(n^2). P.S. Can we do better? On Monday, June 18, 2012 6:10:33 PM UTC+5:30, Jalaj wrote: @KK and hemesh target is not a constant value , it can be any element in array , so you need to do binary search for all (array[i] - (a+b)) to find which increases the complexity to n^3logn. So, i think the n^3 approach which i gave before do it ?? -- Correct me if m wrong On Mon, Jun 18, 2012 at 2:58 PM, Amol Sharma amolsharm...@gmail.comwrote: @hemesh,kk: let's take a test case : arr: 2 4 6 8 arr^2 : 6 8 10 10 12 14(sum of each unique pair in arr[i]) let's say target sum is 26 your solution will return true as they 12+14=26 but in 12 and 14, 8 is common, infact 26 is not possible in the given array can u please elaborate how will you take care of such situation ? @jalaj: yes it's O( (n^3)*logn) @bhavesh: fyi.. log(n^3)=3*log(n)=O(log(n)) so it's same.. :P -- Amol Sharma Final Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/http://facebook.com/amolsharma99 On Mon, Jun 18, 2012 at 12:29 AM, KK kunalkapadi...@gmail.com wrote: @Hemesh : +1 @Jalaj : read Hemesh's solution again it is for 4sum. In short, make a new array having sum of each unique pair of given array. - O(n^2) sort it - O(n^2) for each number bi in new array, binary search (target - bi) in the same array - O(n^2) On Sunday, 17 June 2012 12:41:40 UTC+5:30, Jalaj wrote: The solution which hemesh gave was solution to 3SUM hard problem the best solution for which can be achieved in n^2 . And the original question is a kind of 4SUM hard problem for which best possible solution i think is again n^3 and Amol what you told is not n^3 , finding all triplets will itself take n^3 and doing a binary search again that sums upto n^3*logn. @shashank it is not a variation of 3SUM problem as in 3SUM problem a+b+c = some constant , but in your case it is b+c+d = s-a, where a can change again and again so if you do even apply 3SUM logic to it you will have to do it for every a which will make it n^2*n = n^3 On Sat, Jun 16, 2012 at 2:45 AM, sanjay pandey sanjaypandey...@gmail.com wrote: @hemesh cud u plz elaborate wat is b[k]=a[i]+a[j]...n also ur solution... -- 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+unsubscribe@ **googlegr**oups.com algogeeks%2bunsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/** group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en . -- 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/*
Re: [algogeeks] Re: POSTAGE STAMP PROBLEM
this can be solved in a manner similar to knapsack problem.
u can take the weight of tha knapsack the be the the various amounts u need
to make, 13 cents etc etc. we would need to find a first empty cell.
instead of parameter value, use your own parameter specifying the number
of stamps used.
and u would have to make a smal intuitive change to the manner in which the
cells are populated so as to ensure that it picks a combination which
reaches an exact amount/weight that u need as opposed to a = amount/weight
in regular knapsack.
On Tue, Jun 19, 2012 at 10:41 PM, rammar getam...@gmail.com wrote:
This can be done with DP.
Take an array with values 1 to n.
For every number i, try to make it using the stamps available and the 1 to
i-1 array. Anytime u find that the upper bound is reached, u return.
sudo code.
stamps[K]; - Stamp denominations available.
a[N] - Array of number of stamps required.
a[0] = 0;
For i= 1 to n
{
tempMin = 1000( some large number)
For j = 0 to K - loop over the array storing the number of stamp
denominations.
{
if(stamps[j] = i)
if( tempMin 1 + a[i-j])
tempMin := 1 + a[i-j];
}
if(tempMin maxStampAllowed)
{
return i;
}
else
{
a[i] =tempMin
}
}
This will work with time complexity of O (n*k) . Use of vectors (in c++)
can be helpfule for dynamic arrays.
P.S. Can we do better?
On Tuesday, June 19, 2012 9:25:42 PM UTC+5:30, suzi wrote:
The postage stamp problem is a mathematical riddle that asks what is the
smallest postage value which cannot be placed on an envelope, if the letter
can hold only a limited number of stamps, and these may only have certain
specified face values.
For example, suppose the envelope can hold only three stamps, and the
available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the
solution is 13 cents; since any smaller value can be obtained with at most
three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one
must use at least four stamps.
Is there an algorithm that given the maximum amount of stamps allowed and
the face value of the stamps, one can find the smallest postage that cannot
be placed on the envelope?
--
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/-/a1ykZ8HaDjEJ.
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.
--
Aditya Gupta
B.Tech III yr CSE
IITR
--
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.
