Hello World | PBT CODING | 15 jun

***PBT CODING ONLY ***

Problem 1: 

Problem Statement

The stock span problem is a financial problem where we have a series of n daily price quotes for a

stock and we need to calculate the span of stock’s price for all n days. The span Si of the stock’s

price on a given day i is defined as the maximum number of consecutive days just before the given

day, for which the price of the stock on the current day is less than or equal to its price on the

given day.

Input Format

First line contains n-the number of days. Next line contains n integers-the stock price of each day.

Constraints

1 ≤ N ≤ 10^5 1 ≤ Stock Prices ≤ 10^5

Output Format

Print an array of length N denoting the span for the i-th day.

C++ Program:

#include <bits/stdc++.h>

using namespace std;

void calculateSpan(int price[], int n, int S[])

{

    S[0] = 1;

    for (int i = 1; i < n; i++)

    {

        S[i] = 1; 

        for (int j = i - 1; (j >= 0) &&

                (price[i] >= price[j]); j--)

            S[i]++;

    }

}

void printArray(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

}

int main()

{

   

    int n;cin>>n;int price[n];

    for(int i=0;i<n;i++)

    {

      cin>>price[i];

    }

    int S[n];

    calculateSpan(price, n, S);

 

    printArray(S, n);

 

    return 0;

}

Problem 2:

Problem Statement

Given a square chessboard, the initial position of Knight and position of a target. Find out the

minimum steps a Knight will take to reach the target position.

Note: The initial and the target position co-ordinates of Knight have been given accoring to 1-base

indexing.

Input Format

First line of input contains N-the size of NxN chessboard. Next line of input contains two space

separated integer the x coordinate and y coordinate respectively of knight's position at chessboard

Next line of input contains two space separated integer the x coordinate and y coordinate

respectively of target's position at chessboard.

Constraints

1 <= N <= 1000

1 <= Knight_pos(X, Y), Targer_pos(X, Y) <= N

Output Format

Print the minimum number of steps required by the knight to reach from its current position to the

given target position.

C++ Program:

#include <bits/stdc++.h>

using namespace std;

struct cell {

    int x, y;

    int dis;

    cell() {}

    cell(int x, int y, int dis)

        : x(x), y(y), dis(dis)

    {

    }

};

bool isInside(int x, int y, int N)

{

    if (x >= 1 && x <= N && y >= 1 && y <= N)

        return true;

    return false;

}

int minStepToReachTarget(

    int knightPos[], int targetPos[],

    int N)

{

    int dx[] = { -2, -1, 1, 2, -2, -1, 1, 2 };

    int dy[] = { -1, -2, -2, -1, 1, 2, 2, 1 };

    queue<cell> q;

    q.push(cell(knightPos[0], knightPos[1], 0));

    cell t;

    int x, y;

    bool visit[N + 1][N + 1];

    for (int i = 1; i <= N; i++)

        for (int j = 1; j <= N; j++)

            visit[i][j] = false;

    visit[knightPos[0]][knightPos[1]] = true;

    while (!q.empty()) {

        t = q.front();

        q.pop();

        if (t.x == targetPos[0] && t.y == targetPos[1])

            return t.dis;

        for (int i = 0; i < 8; i++) {

            x = t.x + dx[i];

            y = t.y + dy[i];

            if (isInside(x, y, N) && !visit[x][y]) {

                visit[x][y] = true;

                q.push(cell(x, y, t.dis + 1));

            }

        }

    }

}

int main()

{

    int N;cin>>N;

    int knightPos[2];

    int targetPos[2];

    cin>>knightPos[0]>>knightPos[1]>>targetPos[0]>>targetPos[1];

    cout << minStepToReachTarget(knightPos, targetPos, N);

    return 0;

}

Problem  3:

Problem Statement

Given an expression string x. Examine whether the pairs and the orders of “{“,”}”,”(“,”)”,”“,”” are

correct in exp.

Input Format

A single string s containing the parenthesis.

Constraints

1<=length of string<=1000

Output Format

Print "1" if brackets are balanced else print "0".

C++ Program:

#include <bits/stdc++.h>

using namespace std;

bool areBracketsBalanced(string expr)

{ 

    stack<char> s;

    char x;

    for (int i = 0; i < expr.length(); i++)

    {

        if (expr[i] == '(' || expr[i] == '['

            || expr[i] == '{')

        {

            s.push(expr[i]);

            continue;

        }

        if (s.empty())

            return false;

 

        switch (expr[i]) {

        case ')':

            x = s.top();

            s.pop();

            if (x == '{' || x == '[')

                return false;

            break;

 

        case '}':

            x = s.top();

            s.pop();

            if (x == '(' || x == '[')

                return false;

            break;

 

        case ']':

            x = s.top();

            s.pop();

            if (x == '(' || x == '{')

                return false;

            break;

        }

    }

    return (s.empty());

}

int main()

{

    string expr;

    cin>>expr;

 

    if (areBracketsBalanced(expr))

        cout << "1";

    else

        cout << "0";

    return 0;

}