Day 13 (30 Days of Code)

13 July 2023

As I mentioned before, I have been focusing on data structure for a while and specifically on dynamic programming.

What did I learn?

I first solved my question using brute force but then I used memoization and only after that I came up with the solution using dynamic programming and it's amazing how much of an optimized solution we can get.

• Minimum steps to 1

Given a positive integer 'n', find and return the minimum number of steps that 'n' has to take to get reduced to 1. You can perform any one of the following 3 steps:

1.) Subtract 1 from it. (n = n - ­1) ,
2.) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3.) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).

Input Format:

The first and the only line of input contains an integer value, 'n'.

Output Format:

Print the minimum number of steps.

Constraints:

1 <= n <= 10 ^ 6
Time Limit: 1 sec

Sample Input 1:

4

Sample Output 1:

2

Sample Input 2:

7

Sample Output 2:

3

My solution:

Using Memoization:

int helper(int n, int* arr){

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

    if(arr[n]!=-1){
        return arr[n];
    }

    int a = helper(n-1,arr);
    int b = INT_MAX;
    if(n%2==0){
        b = helper(n/2,arr);
    }

    int c = INT_MAX;
    if(n%3==0){
        c = helper(n/3,arr);
    }

    arr[n] = min(a,min(b,c))+1;

    return arr[n];
}

int countStepsToOne(int n)
{
    int arr[n+1];

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

    return helper(n,arr);
}

Using Dynamic Programming:

int countStepsToOne(int n)
{
    arr[0] = 0;
    arr[1] = 0;

    for(int i=2;i<=n;i++){
        int a = i-1;
        int b = i-1;
        if(i%2==0){
           b = i/2;
        }
        int c = i-1;
        if(i%3==0){
            c = i/3;
        }

        arr[i] = min(arr[a],min(arr[b],arr[c]))+1;
    }

    return arr[n];
}

• Staircase using DP

A child is running up a staircase with n steps and can hop either 1 step, 2 steps or 3 steps at a time. Implement a method to count how many possible ways the child can run up to the stairs. You need to return all possible ways.

Time complexity of your code should be O(n).

Note: Since the answer can be pretty large soo print the answer with mod(10^9 +7)

Input Format:

The first and the only line of input contains an integer value, 'n'.

Output Format:

For each test case print the answer in new line

Constraints:

1 <= T < = 10
1 <= N <= 10^5

Sample Input 1:

2
2
3

Sample Output 1:

2
4

Sample Input 2:

2
5
10

Sample Output 2:

13
274

My solution :

Using Memoization:

int staircase(long long int n,long long int arr[]){

    long long num = pow(10,9)+7;
    if(n==0){
        return 1;
    }
    if(n==1){
        return 1;
    }
    if(n<0){
        return 0;
    }
    if(arr[n]!=-1){
        return arr[n];
    }
    long long int x=staircase(n-1,arr)%num;
    long long int y=staircase(n-2,arr)%num;
    long int z=staircase(n-3,arr)%num;
    arr[n] = (x+y+z)%num;
    return arr[n];
}

int main(){

    // write your code here

    int t;
    cin>>t;

    while(t--){
        long long int n;
        cin>>n;

        long long int arr[n+1];

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

        cout<<staircase(n, arr)<<endl;
    }
    return 0;
}

Using Dynamic Programming

int staircase(long long int n,long long int arr[]){

    if(n<=1){
        return 1;
    }
    int num = 1e9+7;
    arr[0] = 1;

    for(long long int i=1;i<=n;i++){
        long long int a = arr[i-1];
        long long int b = 0;
        if((i-2)>=0){
            b = arr[i-2];
        }
        long long int c = 0;
        if((i-3)>=0){
            c = arr[i-3];
        }
        arr[i] = (a+b+c)%num;
    }
    return arr[n];
}

int main(){

    int t;
    cin>>t;

    while(t--){
        long long int n;
        cin>>n;

        long long int arr[n+1];

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

        cout<<staircase(n, arr)<<endl;
    }
    return 0;
}

• Minimum count

Given an integer N, find and return the count of minimum numbers required to represent N as a sum of squares.

That is, if N is 4, then we can represent it as : {1^2 + 1^2 + 1^2 + 1^2} and {2^2}. The output will be 1, as 1 is the minimum count of numbers required to represent N as sum of squares.

Input Format:

The first and the only line of input contains an integer value, 'N'.

Output Format:

Print the minimum count of numbers required.

Constraints:

0 <= n <= 10 ^ 4

Time Limit: 1 sec

Sample Input 1:

12

Sample Output 1:

3

Explanation :

12 can be represented as : 
A) (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2)

B) (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2) + (1^2)  + (2 ^ 2)

C) (1^2) + (1^2) + (1^2) + (1^2) + (2 ^ 2) + (2 ^ 2)

D) (2 ^ 2) + (2 ^ 2) + (2 ^ 2)

As we can see, the output should be 3.

Sample Input 2:

9

Sample Output 2:

1

My solution:

Using Brute Force:

int minCount(int n)
{
    if(n==0){
        return 0;
    }


    int minValue = INT_MAX;

    for(int i=1;i<=sqrt(n);i++){
        int ans = minCount(n-(i*i));
        minValue = min(minValue,ans);
    }
    return minValue+1;
}

Using Memoization:

int helper(int n,int* arr){
    if(n==0){
        return 0;
    }

    if(arr[n]!=-1){
        return arr[n];
    }

    int minValue = INT_MAX;

    for(int i=1;i<=sqrt(n);i++){
        int ans = helper(n-(i*i), arr);
        minValue = min(minValue,ans);
    }

    arr[n] = minValue+1;
    return arr[n];
}
int minCount(int n)
{
    int* arr = new int[n+1];
    for(int i=0;i<=n;i++){
        arr[i] = -1;
    }
    return helper(n,arr);
}

Using Dynamic Programming:

int minCount(int n)
{
    if(n==0){
        return 0;
    }

    int* arr = new int[n+1];
    arr[0] = 0;

    for(int i=1;i<=n;i++){
        int minValue = INT_MAX;
        for(int j=1;j<=sqrt(i);j++){
            minValue = min(minValue, arr[i-(j*j)]);
        }
        arr[i] = minValue+1;
    }
    return arr[n];
}