题目描述
Hercy 想要为购买第一辆车存钱。他 每天 都往力扣银行里存钱。
最开始,他在周一的时候存入 1
块钱。从周二到周日,他每天都比前一天多存入 1
块钱。在接下来每一个周一,他都会比 前一个周一 多存入 1
块钱。
给定 n
,请你返回在第 n
天结束的时候他在力扣银行总共存了多少块钱。
样例
输入:n = 4
输出:10
解释:第 4 天后,总额为 1 + 2 + 3 + 4 = 10。
输入:n = 10
输出:37
解释:第 10 天后,总额为 (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37。
注意到第二个星期一,Hercy 存入 2 块钱。
输入: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
算法
(数学) $O(1)$
- 令 $m = \frac{n}{7}$ 为完整的周数,$r = n \% 7$ 为最后一个不完整周的天数。
- 通过等差数列求和,可以分别计算出完整的周所获得的钱数。同样,通过等差数列求和,计算出最后一个不完整的周所获得的钱数。
时间复杂度
- 直接用公式计算,故时间复杂度为常数。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int totalMoney(int n) {
const int m = n / 7;
const int r = n % 7;
return 28 * m + 7 * (m - 1) * m / 2 +
(m + 1 + m + r) * r / 2;
}
};