This can be solved using Dynamic Programming approach.
Let MinJump(n) = Minimum number of Jumps required to reach the Nth index
of array A.
then, for 1 i N, MinJump(i) = Min{1 + MinJump(j)} for all j such that
(0= j i) and (j + A[j] = i).
We can prepare an auxiliary array say MinJump[1..N]
Given an array A and the elements stored in an array denotes how much jump
an element can make from that array position. For example there is an array
A = {4 0 0 3 6 5 4 7 1 0 1 2}
Now Ist element which is 4 can make a jump to element 0, 0, 3 and 6. You
are stuck if you end up at 0.
You have to
http://www.geeksforgeeks.org/archives/13209
On Mon, Jul 9, 2012 at 7:02 PM, Akshat Sapra sapraaks...@gmail.com wrote:
Given an array A and the elements stored in an array denotes how much jump
an element can make from that array position. For example there is an array
A = {4 0 0 3 6 5 4 7 1 0
At first look it appears to be a simple problem of discrete binary search.
Take sum of b[i] as the upper_bound and 0 as the lower bound. Then apply a
simple binary search for the number of pages that can be given to a
student. Complexity : O(N log( sum( B ) ) )
On Thu, Jun 14, 2012 at 12:26 PM,
wat constraints does dis bring in the question... Also the books are
arranged in a certain order and this order must never be changed.
does this imply --- a student gets only consecutivly numbered book
if not then
sort the array B in decreasing order in Onlogn
take another array S of k
In a library there are N books with the number of pages in i th book given
by bi . These books are to be distributed among K students such that the
difference between the largest sum of pages in the books assigned to any
student and the smallest sum of number of pages in the books assigned to
If we get even number (probability 1/2) in first throw , so the expected
run is 1
If first throw give ODD (probability 1/2) ,the run needed become 1 + run
needed until second odd number .This last waiting time is 2 .
Thus expected run become (1/2) (1) + (1/2)(1+2) = 2
On Sat, Aug 6, 2011 at
let expected time is T , if we get even(probability 1/2) on first throw so
T become 1 If dont then you are at same place where you started so T =
(1/2) (1) + (1/2) ( 1+T)
= T =2
On Sun, Aug 7, 2011 at 6:05 PM, rajul jain rajuljain...@gmail.com wrote:
If we get even number (probability 1/2)
@Shady :
No...we can say this only at the time when following constraints are
satisfied:
1) *Outcome* of event *should be* *binary*. (In above example Sum can have
binary outcomes only i.e. EVEN or ODD)
2) Random variable x in P(x) should be supported on set {1,2,3,4,} i.e.
It *should start
Hi,
A fair dice is rolled. Each time the value is noted and running sum is
maintained. What is the expected number of runs needed so that the sum is
even ?
Can anyone tell how to solve this problem ? as well as other related
problems of such sort
--
You received this message because you are
Microsoft written:
What is the probability of getting atleast one 6 in 3 attempts of a dice?
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Sat, Aug 6, 2011 at 7:34 AM, shady sinv...@gmail.com wrote:
Hi,
A fair dice is rolled. Each time the value is noted and running sum is
1/6*5/6*5/6*3+ 1/6*1/6*5/6*3+ 1/6*1/6*1/6 =91/216
On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote:
Microsoft written:
What is the probability of getting atleast one 6 in 3 attempts of a dice?
*Muthuraj R
IV th Year , ISE
PESIT , Bangalore*
On Sat, Aug 6, 2011
There are two cases: First if we get even number in first roll.
So P(A)= 1/2
And if We get odd number in second roll, then we need keep rolling untill we
find another odd number.
So, (1/2)*[1/2] + 1/2*1/2*1/2 upto infinity.
On Sat, Aug 6, 2011 at 8:46 PM, Nitin Gupta
Sorry, I mis understood the ques.
On Sat, Aug 6, 2011 at 8:56 PM, Pankaj jatka.oppimi...@gmail.com wrote:
There are two cases: First if we get even number in first roll.
So P(A)= 1/2
And if We get odd number in second roll, then we need keep rolling untill
we find another odd number.
So,
1-(5/6)^3 = 91/216
--
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/-/oZi0vvu8SOgJ.
To post to this group, send email to algogeeks@googlegroups.com.
To
what about the first question guys ?
On Sat, Aug 6, 2011 at 9:00 PM, Nitish Garg nitishgarg1...@gmail.comwrote:
1-(5/6)^3 = 91/216
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
On Sat, Aug 6, 2011 at 8:24 PM, muthu raj muthura...@gmail.com wrote:
Microsoft written:
What is the probability of getting atleast one 6 in 3 attempts of a dice?
probability of not getting 6 = 5/6 * 5/6 * 5/6 = 91/216
so ans 1- 91/216
let me know how was the paper and the pattern
Expected value of a random variable x is defined as E(x)= summation of xp(x)
over all value of x where p(x) is the probability.
so in this case
E(x)= E(2)+E(4)+ E(6)+ .
= 2*1/6 + 4* 3/(6*6)+ 6*10/(6*6*6) + .
On Sat, Aug 6, 2011 at 9:19 PM, sukran dhawan sukrandha...@gmail.comwrote:
Hey sry for my above post. I got a little confused. x is the no of times
dice is rolled so
e(x)=e(1)+e(2)+e(3)+
=1/2 + 2*1/(2*2) + 3*1/(2*2*2) + ..
Please correct me if m wrong..
On Sat, Aug 6, 2011 at 10:54 PM, Kunal Yadav kunalyada...@gmail.com wrote:
Expected value of a random
I think this is correct.
--
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/-/5gZRPfLAwNYJ.
To post to this group, send email to algogeeks@googlegroups.com.
To
E(x)= 1 x (1/2) + 2 x (1/2 x 1/2 (Odd-Odd) + 1/2 x 1/2 (Even-Even) + 3 (1/4
x 1/2 (Odd-Odd-Even)+ 1/4 x 1/2 (Odd-Even-Odd)+ 1/4 x 1/2 (Even-Odd-Odd)+
1/4 x 1/2(Even-Even-Even) )+
E(x)= 1/2 + 1 + 3/2 .
According to me, since the series does not converge, Expectation value does
not exist.
According to me if we get even number in first case then the series will end
there only as we just need an even sum. Similarly in case of e(3) the only
possible sequence for which the sum is even in exactly 3 turns is odd then
even and then odd.
On Sat, Aug 6, 2011 at 11:40 PM, Mukul Gupta
@Kunal: Perhaps, you are right :)
On Sat, Aug 6, 2011 at 11:45 PM, Kunal Yadav kunalyada...@gmail.com wrote:
According to me if we get even number in first case then the series will
end there only as we just need an even sum. Similarly in case of e(3) the
only possible sequence for which the
(for first outcome odd) 1/6 * 3/6 + (for first outcome even) 1/6 * 3/6 =
1/6 so expected 6 cases.
On Sat, Aug 6, 2011 at 8:04 PM, shady sinv...@gmail.com wrote:
Hi,
A fair dice is rolled. Each time the value is noted and running sum is
maintained. What is the expected number of runs needed
In graph theory, a tree is defined as a graph on N nodes,and (N-1)
un-directed edges such that there are no cycles in the graph.Each node
has a single unique path to every other node.
Let D(u,v) be the number of edges in the unique path from node 'u' to
node 'v' (or from node 'v' to 'u' since the
25 matches
Mail list logo
