Why is my code not working? code link in the description

#1

Please help me with this code https://ide.codingblocks.com/s/427411

#2

Hey I don’t understand the logic you used, but there looks to be a flaw if your dp states are same as mine. I’ll share my solution, and please see if this matches with yours or not.
This is what I wrote https://ide.codingblocks.com/s/427450

Here is the explanation.
Here dp[x][y] denotes the probability of having x heads in y tosses.

The transition

dp[x][y] = p[y] * solveDp(x - 1, y - 1) + (1.0 - p[y]) * solveDp(x, y - 1);

is pretty straightforward, you can either have head on the current toss so must have come from
dp[x-1][y-1] or you could have had tail at current toss, so you must have come from dp[x][y-1].

In this loop

for (int i = n; i > n / 2; i–) s += solveDp(i, n);

we sum up all the possiblities.

Like I said dp[x][y] denotes the probability of having x heads in y tosses.

Now what are possible ways of reaching this state?
First observation, y-1 tosses must have been done before this.

Now to get x heads in y tosses, there are two ways.

Either you had x-1 heads in y tosses and got the xth head in the yth toss which is denoted by
(probability of getting head on yth toss) (dp[x-1][y-1]),
or
You already had x heads on y-1 tosses and get tail on the current toss which is equal to
(probability of getting tail on yth toss) (dp[x][y-1]).

#3

I used the one that was shown by sir in the video

#4

instead of a loop, I think he is passing a target ‘x’ heads that we need which is (n+1)/2 and without using a loop we just pass the ‘n’ the number of tosses and the x we need, your code is working but i wanted to know the flaw in mine

#5

You need to perform 1 based indexing. Here I corrected your code https://ide.codingblocks.com/s/427496

1 Like
#6

Thank you so much!!! but can you tell me what if I am using the loop from i=0 to i<n and pass n-1 to the function why does it give an error?

#7

Could you share the code snippet where you are facing the error?

#8

this is my code: https://ide.codingblocks.com/s/427511

#9

It’s running fine. If you are asking why it’s throwing wrong answer, then it is because your base condition doesn’t check for element present at 0th index, it simply returns something where as it should have looked at arr[0]. Sir made 0 as base case because first element is at 1st index and there are no elements at 0th index.

1 Like
#10

thank you so much !!! this is the most help i have gotten on this website:)

1 Like