What are the Minimum Initial Points to Reach Destination ?

Answer : To begin from the upper left corner of a given framework…

What are the Minimum Initial Points to Reach Destination ?

• To begin from the upper left corner of a given framework, one needs to achieve the base right corner.
• Every cell in the grid contains a number, the number may positive or negative.
• We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points.
• We need to find minimum initial points to reach cell (m-1, n-1) from (0, 0) by following these certain set of rules :
• From a cell (i, j) we can move to (i+1, j) or (i, j+1).
• We cannot move from (i, j) if your overall points at (i, j) is <= 0.
• We have to reach at (n-1, m-1) with minimum positive points i.e., > 0.

Sample Code in C++

#include<iostream>
#include<cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {
{-2,-3,3},
{-5,-10,1},
{10,30,-5}
};

int max(int a, int b) {
return (a>b)?a:b;
}

int minInitPoints() {
int minToken[ROW][COL];
int m = ROW, n = COL;

minToken[m-1][n-1] = tokens[m-1][n-1] > 0? 1: abs(tokens[m-1][n-1]) + 1;

for (int i = m-2; i >= 0; i--)    //from last row to first row, fill points
minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);

for (int j = n-2; j >= 0; j--)    //fill last column to first column, fill points
minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

for (int i=m-2; i>=0; i--) {
for (int j=n-2; j>=0; j--) {
int remPoint = min(minToken[i+1][j], minToken[i][j+1]);    //calculate remaining points
minToken[i][j] = max(remPoint - tokens[i][j], 1);
}
}
return minToken;
}

int main() {
cout << "Least Points Required: " << minInitPoints();
}

How to find Second largest element in BST ?

Answer : In an N-ary tree, the second largest value in the given tree to find and return the node…