The original article is available at https://dawnmagnet.top/leetcode/2022/01/15/.

Hercy wants to save money to buy his first car. He deposits money into the Leetcode Bank every day.

He deposits 1 dollar on the first Monday. From Tuesday through Sunday, he deposits 1 dollar more each day than on the previous day. On every following Monday, he deposits 1 dollar more than he deposited on the previous Monday.

Given n, return the total amount of money he has deposited at the end of day n.

Example 1:

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

Example 2:

**Input:** n = 10
**Output:** 37
**Explanation:** After day 10, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that Hercy deposits 2 dollars on the second Monday.

Example 3:

**Input:** n = 20
**Output:** 96
**Explanation:** After day 20, 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

Source: LeetCode Link: https://leetcode-cn.com/problems/calculate-money-in-leetcode-bank Copyright belongs to LeetCode. For commercial use, contact the official copyright holder; for non-commercial use, cite the source as required.

Analysis

#

This is primarily a math problem. We need to compute the sum of a number sequence determined by the input n, so let us examine the pattern of that sequence.

Consider the example from the problem:

\((1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96\)

Two parts are easy to identify:

• The first part consists of complete groups of seven, such as \((1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8)\). Each group contains exactly seven days.
• The other part, such as \((3 + 4 + 5 + 6 + 7 + 8)\), is an incomplete group of seven and can only occur at the end of the sequence.
• According to the problem statement, a complete group of seven represents one week; an incomplete group can only be the final group.

We can split the computation into these two parts:

• For the first part, sum the complete groups. The sums follow a clear pattern: \(28,28+7,28+14,28+21,...\)
• The second part is also an arithmetic progression, but its first term must be calculated from n. Assume \(n=k*7+b\), meaning k complete weeks plus b remaining days. The second progression can then be written as \(k+1,k+2,k+3,...,k+b\).

Both sequences are arithmetic progressions, so we can use the arithmetic-series formula to compute them directly without a loop.

PS: If you do not know the arithmetic-series formula, you can review it in elementary mathematics.

The first progression has first term \(28\), last term \(21+7*k\), and \(k\) terms. The second progression has first term \(k+1\), last term \(k+b\), and \(b\) terms.

Substituting these into the formula gives the final expression \((49 + k * 7) * k / 2 + (2 * k + b + 1) * b / 2\). There is no need to simplify it further, such as distributing k, because that may make the computer perform more operations.

Rust Code

#

impl Solution {
    pub fn total_money(n: i32) -> i32 {
        let k = n / 7;
        let b = n % 7;
        (49 + k * 7) * k / 2 + (2 * k + b + 1) * b / 2
    }
}