Home » Interview coding problems/challenges

# Island Probability

Here, we are going to learn to **find the solution of Island Probability**, calculate the probability of being alive after moving n steps.

Submitted by Divyansh Jaipuriyar, on August 16, 2020

**Problem statement:**

You are standing in some location *(x, y)* on an island, given in form of a matrix of size *N*M*, you are allowed to move in all four directions left, right, up and down. You can move only one step at a time, if you step out of the matrix region then you die. Calculate the probability of being alive after moving *n* steps.

**Problem description:**

The problem wants you to use knowledge of probability, you are standing at some location in the matrix and you are allowed to move in all four directions from the current location as left, right, down and up, but you need to keep in mind that you can only take *K* steps and if you fall out you die that is probability becomes 0 and if you utilized all *K* moves and you are under index range then the probability is 1. So you need to develop some logic that you can maximize the probability of surviving in that island.

**Input:**

The first line of the input is the *T* number of test cases, each test case consists of *N*, size of the given *matrix(N*N)*, and the starting point *(x,y)* in the following line and the number of moves *k* that he has.

**Output:**

You are required to print the probability of person being alive after *n* moves.

**Examples:**

Input: T=1 N=3 x=1,y=1 k=4 Output: 0.375 Input: T=1 N=4 x=2,y=2 k=3 Output: 0.71875

**Solution approach:**

**Recursion Approach:**

We will use a recursive function to solve this problem, we will create a solve function which will take a number of steps that we have, the coordinates as its input and return the probability of being alive if the number of steps remaining is 0 and we are under that matrix boundary then we simply 1 otherwise we will recursively call solve function in all four directions until we are left with 0 moves remaining.

The probability of traveling in all four directions is (0.25) as all have equal probability.

let f(x, y, n) be some function then it can be defined as:

let * f(x, y, n)* be some function then it can be defined as:

**f(x,y,n)=f(x+1,y,n-1)*.25+f(x-1,y,n-1)*.25+f(x,y-1,n-1)*.25+f(x,y+1,n-1)*.25****Time complexity** for above approach in worst case is exponential.

**Space complexity** for above approach in worst case is constant.

**Dynamic Programming Approach:**

In this approach we will use memoization technique to optimize our solution from exponential time to some efficient time, we will create a map for storing values for different states, each time we make a recursive call we will first check it in dp table, if already calculated then simply return it otherwise we calculate it again.

**Time complexity** for the above approach in the worst case is: **O(n*n*n)**

**Space complexity** for the above approach in the worst case is: **O(n*n*n)**

**1) C++ Implementation (Recursion)**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //solve function which will return //probability of being alive. double solve(ll x, ll y, ll k, ll n) { //if remaining moves is 0 and //we are under safe boundary region //then probability is 1. if (k == 0) return 1.0; //initialize probability variable prob //with 0. double prob = 0; //check if we can move in up direction //that is (x-1) index. if (x > 0) prob += solve(x - 1, y, k - 1, n) * (.25); //check if we can move in down direction //that is (x+1) index. if (x < n - 1) prob += solve(x + 1, y, k - 1, n) * (.25); //check if we can move in left direction //that is (y-1) index. if (y > 0) prob += solve(x, y - 1, k - 1, n) * (.25); //check if we can move in right direction //that is (y+1) index. if (y < n - 1) prob += solve(x, y + 1, k - 1, n) * (.25); //finally return overall probability. return prob; } int main() { cout << "Enter number of test cases: "; ll t; cin >> t; while (t--) { cout << "Enter size of N: "; ll n, k; cin >> n; cout << "Enter initial location: "; ll x, y; cin >> x >> y; cout << "Enter moves:\n"; cin >> k; cout << "Probability of being alive: "; cout << solve(x, y, k, n) << "\n"; } return 0; }

**Output:**

Enter number of test cases: 3 Enter size of N: 2 Enter initial location: 0 0 Enter moves: 1 Probability of being alive: 0.5 Enter size of N: 3 Enter initial location: 1 1 Enter moves: 2 Probability of being alive: 0.75 Enter size of N: 3 Enter initial location: 0 0 Enter moves: 3 Probability of being alive: 0.25

**2) C++ Implementation (Dynamic Programming):**

#include <bits/stdc++.h> using namespace std; typedef long long ll; //unordered map for storing //dp state (memorization). unordered_map<string, double> dp; //solve function which will return //probability of being alive. double solve(ll x, ll y, ll k, ll n) { //if remaining moves is 0 and //we are under safe boundary region //then probability is 1. if (k == 0) return 1.0; //string variable for finding whether //given states already calculated or not. string str = ""; str = to_string(x) + to_string(y) + to_string(k); //check if already calculated or not. if (dp.find(str) != dp.end()) return dp[str]; //initialize probability variable prob //with 0. double prob = 0; //check if we can move in up direction //that is (x-1) index. if (x > 0) prob += solve(x - 1, y, k - 1, n) * (.25); //check if we can move in down direction //that is (x+1) index. if (x < n - 1) prob += solve(x + 1, y, k - 1, n) * (.25); //check if we can move in left direction //that is (y-1) index. if (y > 0) prob += solve(x, y - 1, k - 1, n) * (.25); //check if we can move in right direction //that is (y+1) index. if (y < n - 1) prob += solve(x, y + 1, k - 1, n) * (.25); //finally store and return overall probability. return dp[str] = prob; } int main() { cout << "Enter number of test cases: "; ll t; cin >> t; while (t--) { cout << "Enter size of N: "; ll n, k; cin >> n; cout << "Enter initial location: "; ll x, y; cin >> x >> y; cout << "Enter moves:\n"; cin >> k; cout << "Probability of being alive: "; cout << solve(x, y, k, n) << "\n"; } return 0; }

**Output:**

Enter number of test cases: 2 Enter size of N: 3 Enter initial location: 1 1 Enter moves: 4 Probability of being alive: 0.375 Enter size of N: 4 Enter initial location: 2 2 Enter moves: 3 Probability of being alive: 0.71875

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions