30 July 2023

Solved one good dynamic programming problem and 2 easy Leetcode questions.

• Ninja's Training

My approach:

As usual, my very first approach was to try solving it using a greedy approach but that didn't work. For the solution, I wanted to try out all possible ways which means we can use recursion and if there is recursion then we can also use memoization.

After trying the top-down approach I tried the bottom-up approach which is dynamic programming. It was pretty complicated so I had to refer to the solution.

For solution: https://www.youtube.com/watch?v=AE39gJYuRog&list=PLgUwDviBIf0qUlt5H_kiKYaNSqJ81PMMY&index=8&ab_channel=takeUforward

My solution

• Recursion with Memoization

int helper(int day, int lastTask, vector<vector<int>> & points, int** arr){
    if(day==0){
        int maxNum = 0;
        for(int i=0;i<3;i++){
            if(i!=lastTask){
                maxNum = max(maxNum, points[day][i]);
            }
        }
        return maxNum;
    }

    if(lastTask!=3 && arr[day][lastTask]!=-1){
        return arr[day][lastTask];
    }

    int maxPoints = 0;
    for(int i=0;i<3;i++){

        if(i!=lastTask){
            int dayPoints = points[day][i]+helper(day-1,i,points,arr);
            maxPoints = max(maxPoints, dayPoints);
        }
    }

    arr[day][lastTask] = maxPoints;
    return maxPoints;
}

int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.

    int** arr = new int*[n];

    for(int i=0;i<n;i++){
        arr[i] = new int[3];
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<3;j++){
            arr[i][j] = -1;
        }
    }

    return helper(n-1,3,points,arr);
}

• Dynamic Programming

int ninjaTraining(int n, vector<vector<int>> &points)
{
    // Write your code here.

    int** arr = new int*[n];

    for(int i=0;i<n;i++){
        arr[i] = new int[4];
    }

    arr[0][0] = max(points[0][1], points[0][2]);
    arr[0][1] = max(points[0][0], points[0][2]);
    arr[0][2] = max(points[0][0], points[0][1]);
    arr[0][3] = max(points[0][0], max(points[0][1], points[0][2]));

    for(int i=1;i<n;i++){
        for(int j=0;j<4;j++){
            arr[i][j] = 0;
            for(int k=0;k<3;k++){
                if(k!=j){
                    int point = points[i][k]+arr[i-1][k];
                    arr[i][j] = max(arr[i][j],point);
                }     
            }   
        } 
    }

    return arr[n-1][3];    
}

---

• Arranging Coins

My approach:

It was an easy question. My very first solution took O(n) time to implement so I decided to do it just in O(logn). At first, I tried using the sqrt function but then I was getting errors so I used the classic binary search approach.

My solution:

• Linear Time complexity

class Solution {
public:
    int arrangeCoins(int n) {

        if(n<=1){
            return n;
        }

        int row = 0;
        int count = 1;

        while(n>0){
            n = n-count;
            count++;
            row++;
        }

        if(n<0){
            return row-1;
        }

        return row;


    }
};

• Using the sqrt/pow function but I was getting an overflow error

class Solution {
public:
    int arrangeCoins(int n) {

        int x = 1+4*2*n;
        float root = pow(x,0.5)-1;
        int ans = root/2;

        return ans;
    }
};

• Using Binary search

class Solution {
public:
    int arrangeCoins(int n) {

        long long i = 0;
        long long j = n;

        while(i<=j){
            long long mid = (i+j)/2;
            if((mid*(mid+1))/2>n){
                j = mid-1;
            }else{
                i = mid+1;
            }
        }

        return i-1;
    }
};