Calculate Money in Bank- A Greedy algorithm Problem in C++

This problem is about a greedy algorithm we will going to solve this problem and will learn about the concepts and algorithm used and then will see its implementation in C++.

Problem description

Harsh wants to celebrate his birthday this time with his own money so he started saving for that. He puts some amount in the bank every day. He starts by putting in $1 on Monday, then $2 on Tuesday then $3 on Wednesday, and so on till the end of the week. Then on next Monday, he puts $2, then $3 on Tuesday Every day from Wednesday to Sunday, he will put in $1 more than the day before and this goes on. every subsequent week amount increases by one on each day. Given n, return the final total amount he will have in the bank at the end of the nth day.

Example 1:

Input:

 n = 4

Output:

 10

Explanation:

 After the 4thday, the total is 1 + 2 + 3 + 4 = 10.

Example 2:

Input:

 n = 10

Output:

 37

Explanation:

After the 10thday, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd  Monday, Harsh only puts in $2.

Example 3:

Input:

 n = 20

Output:

 96

Explanation:

 After the 20thday, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.

Constraints:

  • 1 <= n <= 500

Approach

Now as mentioned in the problem statement we have to return the total money he had in the bank on an nth day and for 1st week the amount on every day is Monday $1, Tuesday $2, Wednesday $3, Thursday $4, Friday $5, Saturday $6, Sunday $7. So using the summation formula i.e n(n+1)/2 we get a total of 28 after 1st week. Now according to a question on every subsequent week the per day amount increases by one that it was before. So the total amount will also increase by 7 every week i.e on 1st week it was 28 in 2nd week it will be 28+7 = 35 on 3rd week it will be 35+7=42 and so on from here, we get a conclusion that at the end of Xth week the total amount would be 28+(X-1)*7. Now suppose after Xth week there are certain days left who’s amount is to be calculated, let say n=10 so after 1st week 3 days are left so for these 3 days also we had to calculate the amount and add it to the result and since these three days are in the second week and their amount is also increased by 1 from their previous week values so for these remaining days we can derive the formula (1+X) + (2+X) + (3+X)…….till remaining days.

Implementation

#include<bits/stdc++.h>
using namespace std;

int totalMoney(int n)
{
        int week=n/7;// week
        int rem=n%7; // remaining days after week

        int sum=0;
        for(int i=1;i<=week;i++)
            sum+=(28+(i-1)*7);  // calculate total till that week

        for(int i=1;i<=rem;i++) // calculate for remaining days
            sum+=(i+week);

        return sum;
}

int main(){
    int n;
    cin>>n;
    cout<<totalMoney(n);
return 0;
}

Sample case 

For n=10 After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37, after applying the formula we get week=1 and rem=3 so sum=28+(1-1)*7=28 and for remaining days we get sum= sum+(1+1)+(1+2)+(3+1) so final answer is 28+9 = 37 i.e Harsh will have 37$ at the end of 10th day in the bank.

Hope you understand the implementation and algorithm used! Thank you.

 

Leave a Reply

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