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 nth day.
Example 1:
Input: n = 4 Output: 10 Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.
Example 2:
Input: n = 10 Output: 37 Explanation: After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.
Example 3:
Input: n = 20 Output: 96 Explanation: After the 20th 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 <= 1000Problem Overview: You deposit money into the LeetCode bank every day following a pattern. On Monday you start with $1, Tuesday $2, ... Sunday $7. Each new week starts one dollar higher than the previous Monday. Given n days, compute the total amount saved.
Approach 1: Iterative Simulation (O(n) time, O(1) space)
The most direct solution simulates the deposit process day by day. Track the current week's starting value and increment the daily deposit as the week progresses. Every time seven days pass, increase the starting value for the next week. You iterate from day 1 to n, add the appropriate deposit for each day, and accumulate the total. This approach mirrors the problem statement exactly and is easy to implement using simple arithmetic and a loop.
This method works well because the constraints are small enough that iterating through n days is trivial. The logic typically tracks two values: the starting deposit for the week and the day offset inside the week. Concepts like basic iteration and counters make this a good introductory problem for simulation and simple math reasoning.
Approach 2: Mathematical Formula (O(1) time, O(1) space)
The optimal solution avoids iterating through each day by recognizing a repeating weekly structure. Every week contains an arithmetic sequence of seven deposits. If n days are given, first compute the number of full weeks w = n / 7 and remaining days r = n % 7. The total contribution of full weeks forms a pattern where each week's starting value increases by one.
The weekly deposits themselves follow an arithmetic progression: week 1 sums to 28 (1 through 7), week 2 sums to 35 (2 through 8), and so on. The total for all full weeks can be derived using arithmetic series formulas. After computing that value, add the contribution from the remaining r days starting from w + 1. This converts a day-by-day simulation into a few constant-time calculations using properties of mathematical series.
Recommended for interviews: Start with the iterative simulation to show you understand the deposit pattern and can translate the rules into code. Then optimize with the mathematical formula. Interviewers often expect the O(1) solution because it demonstrates pattern recognition and comfort with arithmetic series instead of relying only on loops.
The iterative approach involves simulating each day in a loop, tracking both the weeks and individual days. We'll add the appropriate amount of money for each day based on the rules provided. This approach leverages basic looping constructs and conditionally increments the sums based on the day of the week.
This C solution uses a for loop to iterate through each day until n. It calculates the current 'week' number and the 'day of the week' using modulo arithmetic. It adds the appropriate amount for that day to a running total.
Time Complexity: O(n), where n is the number of days. Each day is processed once.
Space Complexity: O(1), only a constant amount of space is used.
The mathematical approach seeks to minimize iterations by using formulae to directly compute sums based on weeks, leveraging arithmetic series properties. This method is typically more efficient and concise.
This solution calculates the contribution of complete weeks and the remaining days separately using arithmetic sum formulae. It computes the sum of weeks' contributions and adds the extra days with incremental daily increases.
Time Complexity: O(1).
Space Complexity: O(1).
According to the problem description, the deposit situation for each week is as follows:
Week 1: 1, 2, 3, 4, 5, 6, 7
Week 2: 2, 3, 4, 5, 6, 7, 8
Week 3: 3, 4, 5, 6, 7, 8, 9
...
Week k: k, k+1, k+2, k+3, k+4, k+5, k+6
Given n days of deposits, the number of complete weeks is k = \lfloor n / 7 \rfloor, and the remaining days is b = n \mod 7.
The total deposit for the complete k weeks can be calculated using the arithmetic sequence sum formula:
$
S_1 = \frac{k}{2} times (28 + 28 + 7 times (k - 1))
The total deposit for the remaining b days can also be calculated using the arithmetic sequence sum formula:
S_2 = \frac{b}{2} times (k + 1 + k + 1 + b - 1)
The final total deposit amount is S = S_1 + S_2.
The time complexity is O(1) and the space complexity is O(1)$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), where n is the number of days. Each day is processed once. |
| Mathematical Approach | Time Complexity: O(1). |
| Math | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(n) | O(1) | Best for clarity and quick implementation when constraints are small |
| Mathematical Formula | O(1) | O(1) | Preferred in interviews to demonstrate pattern recognition and arithmetic series optimization |
Calculate Money in Leetcode Bank - Leetcode 1716 - Python • NeetCodeIO • 8,521 views views
Watch 9 more video solutions →Practice Calculate Money in Leetcode Bank with our built-in code editor and test cases.
Practice on FleetCode