1716. Calculate Money in Leetcode Bank (Easy)

Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.

He starts by putting in $1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday.

Given n, return the total amount of money he will have in the Leetcode bank at the end of the n^th day.

Example 1:

Input: n = 4
Output: 10
Explanation: After the 4^th day, the total is 1 + 2 + 3 + 4 = 10.

Example 2:

Input: n = 10
Output: 37
Explanation: After the 10^th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2^nd Monday, Hercy only puts in $2.

Example 3:

Input: n = 20
Output: 96
Explanation: After the 20^th day, 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 <= 1000

Related Topics:
Math, Greedy

Solution 1. Brute Force

// OJ: https://leetcode.com/problems/calculate-money-in-leetcode-bank/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int totalMoney(int n) {
        int s = 1, ans = 0;
        while (n > 0) {
            for (int i = 0; i < 7 && n-- > 0; ++i) ans += s + i;
            s++;
        }
        return ans;
    }
};

Solution 2. Math

We have f = n / 7 full weeks.

The first week we deposit (1 + 7) * 7 / 2 = 28 dollars.

The wth week we deposit (w + w + 6) * 7 / 2 = (w + 3) * 7 dollars, the w + 1th week we deposit 7 dollars more.

So the money we deposit each week is also an arithmetic sequence, whose sum is (28 + 28 + 7 * (f - 1)) * f / 2 = (49 + 7 * f) * f / 2.

The last non-full week has d = n % 7 days. We deposit f + 1 dollars on its Monday, so we deposit (f + 1 + (f + 1 + d - 1)) * d / 2 = (2 * f + d + 1) * d / 2 dollars for this week.

So the final answer is (49 + 7 * f) * f / 2 + (2 * f + d + 1) * d / 2.

// OJ: https://leetcode.com/problems/calculate-money-in-leetcode-bank/
// Author: github.com/lzl124631x
// Time: O(1)
// Space: O(1)
class Solution {
public:
    int totalMoney(int n) {
        int f = n / 7, d = n % 7;
        return (49 + 7 * f) * f / 2 + (2 * f + d + 1) * d / 2;
    }
};