What is the most efficient way to solve the Calculate Money in Leetcode Bank problem?

The most efficient way is to use a mathematical formula that calculates the total sum directly, rather than simulating each deposit day by day.

What is the pattern behind Hercy's weekly deposits?

Hercy increases his deposit by $1 each day from Monday to Sunday, and every Monday, his deposit amount increases by $1 compared to the previous Monday.

Can I simulate the process for each day to solve this problem?

While simulating the process works, it can be inefficient. A mathematical formula gives a much faster O(1) solution.

How do I calculate the total amount at the end of the nth day?

You calculate the total by simulating the deposits for each week or use a mathematical formula that accounts for the increasing deposits per week.

What is the time complexity of the optimal solution for the Calculate Money in Leetcode Bank problem?

The optimal solution has a time complexity of O(1) since it uses a formula to directly compute the total amount without iterating over each day.

#1716

Easy

auto_awesome数学·driven

LeetCode 题解工作台

计算力扣银行的钱

Hercy 想要为购买第一辆车存钱。他每天都往力扣银行里存钱。最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比前一个周一多存入 1 块钱。给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。示例 1：…

数学

题目描述

Hercy 想要为购买第一辆车存钱。他每天都往力扣银行里存钱。

最开始，他在周一的时候存入 1 块钱。从周二到周日，他每天都比前一天多存入 1 块钱。在接下来每一个周一，他都会比 前一个周一 多存入 1 块钱。

给你 n ，请你返回在第 n 天结束的时候他在力扣银行总共存了多少块钱。

示例 1：

输入：n = 4
输出：10
解释：第 4 天后，总额为 1 + 2 + 3 + 4 = 10 。

示例 2：

输入：n = 10
输出：37
解释：第 10 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37 。注意到第二个星期一，Hercy 存入 2 块钱。

示例 3：

输入：n = 20
输出：96
解释：第 20 天后，总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96 。

提示：

1 <= n <= 1000

lightbulb

解题思路

方法一：数学

根据题目描述，每周的存款情况如下：

第 1 周：1, 2, 3, 4, 5, 6, 7
第 2 周：2, 3, 4, 5, 6, 7, 8
第 3 周：3, 4, 5, 6, 7, 8, 9
...
第 k 周：k, k+1, k+2, k+3, k+4, k+5, k+6

存款天数为 $n$ ，那么完整的周数为 $k = \lfloor n / 7 \rfloor$ ，剩余天数为 $b = n \mod 7$ 。

完整的 $k$ 周的存款总额，可以通过等差数列求和公式计算：

S_1 = \frac{k}{2} \times (28 + 28 + 7 \times (k - 1))

剩余的 $b$ 天的存款总额，同样可以通过等差数列求和公式计算：

S_2 = \frac{b}{2} \times (k + 1 + k + 1 + b - 1)

最终的总存款金额为 $S = S_1 + S_2$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

class Solution:
    def totalMoney(self, n: int) -> int:
        k, b = divmod(n, 7)
        s1 = (28 + 28 + 7 * (k - 1)) * k // 2
        s2 = (k + 1 + k + 1 + b - 1) * b // 2
        return s1 + s2

speed

复杂度分析

指标	值
时间	O(1)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain the pattern behind the deposits?
question_mark
Does the candidate attempt to use a direct mathematical formula for efficiency?
question_mark
How well does the candidate simulate or optimize the process without looping through all the days?

warning

常见陷阱

外企场景

error
Failing to account for the weekly increase on Mondays.
error
Incorrectly simulating the deposit amount for each day of the week.
error
Using an inefficient solution with a time complexity greater than O(1).

swap_horiz

进阶变体

外企场景

arrow_right_alt
Extend the problem to handle multiple months of deposits.
arrow_right_alt
Change the weekly increment pattern to something more complex, such as an exponential growth.
arrow_right_alt
Increase the maximum value of n to test the efficiency of the solution.

help

常见问题

外企场景

继续练习

#1728 猫和老鼠 II #1735 生成乘积数组的方案数 #1739 放置盒子