A person starts walking from position X = 0, find the probability to reach exactly on X = N if she can only take either 2 steps or 3 steps. Probability for step length 2 is given i.e. P, probability for step length 3 is 1 – P.
Examples :
Input : N = 5, P = 0.20
Output : 0.32
Explanation :-
There are two ways to reach 5.
2+3 with probability = 0.2 * 0.8 = 0.16
3+2 with probability = 0.8 * 0.2 = 0.16
So, total probability = 0.32.
It is a simple dynamic programming problem. It is simple extension of this problem :- count-ofdifferent-ways-express-n-sum-1-3-4
Below is the implementation of the above approach.
C++
// CPP Program to find probability to // reach N with P probability to take// 2 steps (1-P) to take 3 steps#include <bits/stdc++.h>using namespace std;// Returns probability to reach Nfloat find_prob(int N, float P){ double dp[N + 1]; dp[0] = 1; dp[1] = 0; dp[2] = P; dp[3] = 1 - P; for (int i = 4; i <= N; ++i) dp[i] = (P)*dp[i - 2] + (1 - P) * dp[i - 3]; return dp[N];}// Driver codeint main(){ int n = 5; float p = 0.2; cout << find_prob(n, p); return 0;} |
Java
// Java Program to find probability to // reach N with P probability to take// 2 steps (1-P) to take 3 stepsimport java.io.*;class GFG { // Returns probability to reach N static float find_prob(int N, float P) { double dp[] = new double[N + 1]; dp[0] = 1; dp[1] = 0; dp[2] = P; dp[3] = 1 - P; for (int i = 4; i <= N; ++i) dp[i] = (P) * dp[i - 2] + (1 - P) * dp[i - 3]; return ((float)(dp[N])); } // Driver code public static void main(String args[]) { int n = 5; float p = 0.2f; System.out.printf("%.2f",find_prob(n, p)); }}/* This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 Program to find # probability to reach N with# P probability to take 2 # steps (1-P) to take 3 steps# Returns probability to reach Ndef find_prob(N, P) : dp =[0] * (n + 1) dp[0] = 1 dp[1] = 0 dp[2] = P dp[3] = 1 - P for i in range(4, N + 1) : dp[i] = (P) * dp[i - 2] + (1 - P) * dp[i - 3] return dp[N]# Driver coden = 5p = 0.2print(round(find_prob(n, p), 2))# This code is contributed by Nikita Tiwari. |
C#
// C# Program to find probability to // reach N with P probability to take// 2 steps (1-P) to take 3 stepsusing System;class GFG { // Returns probability to reach N static float find_prob(int N, float P) { double []dp = new double[N + 1]; dp[0] = 1; dp[1] = 0; dp[2] = P; dp[3] = 1 - P; for (int i = 4; i <= N; ++i) dp[i] = (P) * dp[i - 2] + (1 - P) * dp[i - 3]; return ((float)(dp[N])); } // Driver code public static void Main() { int n = 5; float p = 0.2f; Console.WriteLine(find_prob(n, p)); }}/* This code is contributed by vt_m.*/ |
Javascript
<script>// JavaScript Program to find probability to // reach N with P probability to take// 2 steps (1-P) to take 3 steps // Returns probability to reach N function find_prob(N, P) { let dp = []; dp[0] = 1; dp[1] = 0; dp[2] = P; dp[3] = 1 - P; for (let i = 4; i <= N; ++i) dp[i] = (P) * dp[i - 2] + (1 - P) * dp[i - 3]; return (dp[N]); }// Driver Code let n = 5; let p = 0.2; document.write(find_prob(n, p)); // This code is contributed by chinmoy1997pal.</script> |
PHP
<?php// PHP Program to find probability to // reach N with P probability to take// 2 steps (1-P) to take 3 steps// Returns probability to reach Nfunction find_prob($N, $P){ $dp; $dp[0] = 1; $dp[1] = 0; $dp[2] = $P; $dp[3] = 1 - $P; for ($i = 4; $i <= $N; ++$i) $dp[$i] = ($P) * $dp[$i - 2] + (1 - $P) * $dp[$i - 3]; return $dp[$N];}// Driver code$n = 5;$p = 0.2;echo find_prob($n, $p);// This code is contributed by mits.?> |
Output
0.32
Time Complexity: O(n)
Auxiliary Space: O(n)
Efficient approach: Space optimization O(1)
In the previous approach, the current value dp[i] only depends on the previous 2 values of dp i.e. dp[i-2] and dp[i-3]. So to optimize the space complexity we can store the previous 4 values of Dp in 4 variables his way, the space complexity will be reduced from O(N) to O(1)
Implementation Steps:
- Initialize variables for dp[0], dp[1], dp[2], and dp[3] as 1, 0, P, and 1-P respectively.
- Iterate from i = 4 to N and use the formula dp[i] = (P)*dp[i – 2] + (1 – P) * dp[i – 3] to compute the current value of dp.
- After each iteration, update the values of dp0, dp1, dp2, and dp3 to dp1, dp2, dp3, and curr respectively.
- Return the final value of curr.
Implementation:
C++
// CPP Program to find probability to// reach N with P probability to take// 2 steps (1-P) to take 3 steps#include <bits/stdc++.h>using namespace std;// Returns probability to reach Nfloat find_prob(int N, float P){ // to store current value double curr; // store previous 4 values of DP double dp0 = 1, dp1=0, dp2=P, dp3= 1-P; // iterate over subproblems to get // current solution from previous computations for (int i = 4; i <= N; ++i){ curr = (P)*dp2 + (1 - P) * dp1; // assigning values to iterate further dp0=dp1; dp1=dp2; dp2=dp3; dp3=curr; } // return final answer return curr;}// Driver codeint main(){ int n = 5; float p = 0.2; cout << find_prob(n, p); return 0;} |
Java
import java.util.*;public class Main { // Returns probability to reach N static float find_prob(int N, float P) { // to store current value double curr; // store previous 4 values of DP double dp0 = 1, dp1 = 0, dp2 = P, dp3 = 1 - P; // iterate over subproblems to get // current solution from previous computations for (int i = 4; i <= N; ++i) { curr = (P) * dp2 + (1 - P) * dp1; // assigning values to iterate further dp0 = dp1; dp1 = dp2; dp2 = dp3; dp3 = curr; } // return final answer return (float) curr; } // Driver code public static void main(String[] args) { int n = 5; float p = 0.2f; System.out.println(find_prob(n, p)); }} |
Python3
# Function to find the probability to reach N with P probability to# take 2 steps and (1-P) to take 3 stepsdef find_prob(N, P): # Initialize variables to store current and previous values curr = 0.0 # Initialize previous 4 values of DP dp0, dp1, dp2, dp3 = 1.0, 0.0, P, 1 - P # Iterate over subproblems to calculate the # current solution from previous computations for i in range(4, N + 1): curr = P * dp2 + (1 - P) * dp1 # Update values for the next iteration dp0, dp1, dp2, dp3 = dp1, dp2, dp3, curr # Round the final answer to 2 decimal places return round(curr, 2)# Driver codeif __name__ == "__main__": n = 5 p = 0.2 print(find_prob(n, p)) |
Javascript
// Returns probability to reach Nfunction find_prob(N, P) { // to store current value let curr; // store previous 4 values of DP let dp0 = 1, dp1 = 0, dp2 = P, dp3 = 1 - P; // iterate over subproblems to get // current solution from previous computations for (let i = 4; i <= N; ++i) { curr = (P * dp2) + ((1 - P) * dp1); // assigning values to iterate further dp0 = dp1; dp1 = dp2; dp2 = dp3; dp3 = curr; } // return final answer return curr;}// Driver codelet n = 5;let p = 0.2;console.log(find_prob(n, p).toFixed(2)); |
Output
0.32
Time complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
