@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,
@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
@ 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
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)
@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
@ *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
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
@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
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
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
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
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
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
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
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
@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
@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
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
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
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
20 matches
Mail list logo