| |

Question: Polly went to his nearby bank to withdraw money. – Free Chegg Question Answer

Polly went to his nearby bank to withdraw money.

To make withdrawals difficult during the covid restrictions, the bank allows its customers to withdraw only one of the following amounts in one operation :

• 1 coin

• 6 coins, 6^2 (=36) coins, 6^3 (=216) coins,…(i.e withdraw any power of 6)

• 9 coins, 9^2(=81) coins, 9^3(=729) coins, …(i.e withdraw any power of 9)

Your task is to help Polly minimize the number of operations required to withdraw exactly N coins in total.

Input Format

The first line contains a single integer N.
1<=N<=100000

Output Format

Print minimum number of operations required.

Testcase Input

127

Testcase Output
4

By withdrawing 1 coin, 9 coins, 36 coins and 81 coins, we can wiwdraw 127 coins in four operations.

Testcase Input
3

Test case Output

3

By withdrawing 1 coin three times, we can withdraw 3 coins in three operations.

#include <<math>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
//Write your code here
}

Write code in C++
URGENT

Transcribed text From Image: 

Expert Chegg Question Answer:

free chegg question answer
Smart Teacher From Answerie.com
Answer:

Answer


We can do this using dp, where the state of the dp will represent the amount that needs to be withdrawn and the value that dp array will store will be the minimum transactions that are required to withdraw that amount. In programming terms:

dp[i] = minimum transactions required to withdraw amount i.

dp[0] = 0 as no transaction is required to withdraw 0 amount.

Here is my c++ code:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> dp;

int intlog(double base, double x) { //to find log6 and log9
    return (int)(log(x)/log(base));
}

int minimumTransactions(int n)
{
    if(n == 0) //base case 
        return 0;
    if(dp[n] != -1) //if the answer is already stored in dp[n]
        return dp[n];
    int ans1 = 1 + minimumTransactions(n-1); //if we withdraw 1 coin 
    if(n >= 6)
    {
        int x = intlog(6, n); //we withdraw maximum 6^x amount that is less than or equal to n 
        ans1 = min(ans1, 1 + minimumTransactions(n-pow(6,x)));
    }
    if(n >= 9)
    {
        int x = intlog(9, n); //we withdraw maximum 9^x amount that is less than or equal to n 
        ans1 = min(ans1, 1 + minimumTransactions(n-pow(9,x)));
    }
    return dp[n] = ans1; //storing the answer in dp array 
}

int main()
{
    int n;
    cin>>n;
    dp.resize(n+1,-1);
    cout<<minimumTransactions(n);
}

Here is a sample output:

Status Successfully executed Date 2021-09-19 12:10:02 Time 0 sec Input 127 Output 4

The output is correct, hence our code works perfectly fine!

If you have any queries please ask in comments.

Hope you like the solution 🙂


Free Chegg Question Answer

Leave a Reply

Your email address will not be published. Required fields are marked *