#1716

Easy

auto_awesomeMath-driven solution strategy

LeetCode Problem Workspace

Calculate Money in Leetcode Bank

Calculate the total amount of money in the Leetcode bank at the end of the nth day, based on a weekly increasing deposit pattern.

math

Problem Statement

Hercy deposits money in the Leetcode bank daily, starting with $1 on Monday. Each subsequent day of the week, he deposits$ 1 more than the day before. On each new Monday, he increases his deposit by $1 compared to the previous Monday.

Given an integer n representing the nth day, return the total amount of money Hercy will have in the Leetcode bank after n days, based on this increasing weekly pattern.

Examples

Example 1

Input: n = 4

Output: 10

After the 4th day, the total is 1 + 2 + 3 + 4 = 10.

Example 2

Input: n = 10

Output: 37

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

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 <= 1000

Solution Approach

Simulate the Deposit Process

Start by simulating Hercy's deposits day by day. Track the amount deposited each day and adjust the deposit for the following week by incrementing the deposit amount on Mondays. This approach will directly follow the problem's weekly deposit structure.

Utilize a Running Sum

Maintain a running sum of the total money deposited over the days. For each day, simply add the correct amount based on the weekly increment pattern. This allows for efficient computation.

Optimize with Formula

Instead of iterating through each day, use a formula derived from the increasing arithmetic series to calculate the total sum more efficiently. This solution avoids unnecessary loops and gives an O(1) time complexity.

Complexity Analysis

Metric	Value
Time	O(1)
Space	O(1)

The time complexity is O(1) because we can directly compute the total using a mathematical formula rather than simulating each day. Space complexity is also O(1) as we do not need additional data structures beyond a few variables to track the deposit amount.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

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

FAQ

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.

terminal

Solution

Solution 1: Math

According to the problem description, the deposit situation for each week is as follows:

1

2

3

4

5

6

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

Continue Practicing

#1728 cat and mouse ii #1735 count ways to make array with product #1739 building boxes