LeetCode 1716 - Calculate Money in Leetcode Bank

The problem describes a repeating weekly saving pattern. Hercy deposits money into the LeetCode bank every day, and the amount increases in a structured way. On the very first Monday, he deposits 1 dollar. Each following day in the same week increases by 1.

leetcodeeasymath

LeetCode Problem 1716

Difficulty: 🟢 Easy
Topics: Math

Solution

Problem Understanding

The problem describes a repeating weekly saving pattern. Hercy deposits money into the LeetCode bank every day, and the amount increases in a structured way.

On the very first Monday, he deposits 1 dollar. Each following day in the same week increases by 1. That means the first week looks like this:

  • Monday: 1
  • Tuesday: 2
  • Wednesday: 3
  • Thursday: 4
  • Friday: 5
  • Saturday: 6
  • Sunday: 7

When the next Monday arrives, the starting amount also increases by 1. So the second week becomes:

  • Monday: 2
  • Tuesday: 3
  • Wednesday: 4
  • Thursday: 5
  • Friday: 6
  • Saturday: 7
  • Sunday: 8

This pattern continues every week.

The input n represents the number of days Hercy has been saving money. The task is to compute the total amount deposited after exactly n days.

The constraints are very small:

  • 1 <= n <= 1000

Since n is at most 1000, even a direct simulation of every day is efficient enough. However, the problem also contains a clear mathematical structure, which allows us to derive a cleaner and more elegant solution.

Important edge cases include partial weeks, exact multiples of seven days, and the smallest possible input value. A naive implementation can easily make off by one mistakes when transitioning between weeks or calculating the daily increment.

Approaches

Brute Force Approach

The brute force solution simulates the deposit process day by day.

We maintain:

  • The current week's Monday value
  • The current day's deposit
  • The running total

For each day:

  1. Add the current deposit to the answer.
  2. Increase the daily deposit by 1.
  3. After every seventh day, reset the daily deposit so the next Monday starts one larger than the previous Monday.

This approach works because it directly follows the rules given in the problem statement. Every deposited value is generated exactly as described.

Although this solution is perfectly acceptable for the given constraints, it still performs unnecessary day by day simulation. Since the deposit pattern forms arithmetic sequences, we can compute totals mathematically instead.

Optimal Mathematical Approach

The key observation is that each full week forms an arithmetic sequence.

For example:

  • Week 1 sum = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
  • Week 2 sum = 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35
  • Week 3 sum = 3 + 4 + 5 + 6 + 7 + 8 + 9 = 42

Each week's total increases by 7.

We can split the total number of days into:

  • Full weeks
  • Remaining days

If:

  • weeks = n // 7
  • days = n % 7

Then:

  1. Compute the contribution from all complete weeks.
  2. Compute the contribution from the remaining days of the partial week.
  3. Add both together.

This avoids explicit simulation and produces a concise mathematical solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Simulates deposits day by day
Optimal O(1) O(1) Uses arithmetic progression formulas

Algorithm Walkthrough

  1. Compute the number of complete weeks using integer division.
weeks = n // 7

Each complete week contributes a predictable arithmetic sequence. 2. Compute the number of leftover days after the complete weeks.

days = n % 7

These represent the deposits in the final partial week. 3. Compute the total contribution from all complete weeks.

The first week's sum is 28.

Every next week increases by 7.

Therefore, the sequence of weekly sums is:

28, 35, 42, ...

This is an arithmetic progression.

The formula becomes:

full_weeks_total =
    weeks * 28 + 7 * (weeks * (weeks - 1) // 2)

The second term accounts for the increasing Monday starting values. 4. Compute the contribution from the remaining days.

The next Monday starts at:

weeks + 1

The remaining deposits form another arithmetic sequence:

(weeks + 1), (weeks + 2), ...

The sum is:

remaining_total =
    days * (weeks + 1) + days * (days - 1) // 2
  1. Return the sum of both parts.
answer = full_weeks_total + remaining_total

Why it works

The algorithm works because the deposits follow arithmetic progressions both across weeks and within each week.

Each complete week starts one dollar higher than the previous week, creating a predictable increase in weekly totals. The remaining days also form a consecutive arithmetic sequence starting from the current week's Monday value.

Since arithmetic progression formulas exactly model the deposit pattern, the computed result always matches the actual deposited amount.

Python Solution

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7
        days = n % 7

        full_weeks_total = (
            weeks * 28
            + 7 * (weeks * (weeks - 1) // 2)
        )

        remaining_total = (
            days * (weeks + 1)
            + days * (days - 1) // 2
        )

        return full_weeks_total + remaining_total

The implementation first separates the input into complete weeks and leftover days.

The variable weeks represents how many full Monday to Sunday cycles exist. The variable days stores how many extra days remain afterward.

The expression for full_weeks_total computes the total contribution from all complete weeks. Each week contributes a base sum of 28, and each later week starts one dollar higher than the previous week. The arithmetic progression formula efficiently computes this cumulative increase.

The expression for remaining_total computes the deposits for the partial week. The deposits start at weeks + 1, because every completed week increases the Monday starting value by 1.

Finally, the function returns the sum of both components.

Go Solution

func totalMoney(n int) int {
    weeks := n / 7
    days := n % 7

    fullWeeksTotal :=
        weeks*28 +
            7*(weeks*(weeks-1)/2)

    remainingTotal :=
        days*(weeks+1) +
            days*(days-1)/2

    return fullWeeksTotal + remainingTotal
}

The Go implementation follows exactly the same mathematical logic as the Python version.

Go uses integer arithmetic automatically for these operations, so there is no need for special handling. Since the maximum value of n is only 1000, integer overflow is not a concern.

Unlike Python, Go requires explicit variable declarations using :=.

Worked Examples

Example 1

Input:

n = 4

Compute:

Variable Value
weeks 0
days 4

Full weeks contribution:

0

Remaining days contribution:

4 * (0 + 1) + 4 * 3 / 2
= 4 + 6
= 10

Final answer:

10

Deposits:

Day Deposit Running Total
1 1 1
2 2 3
3 3 6
4 4 10

Example 2

Input:

n = 10

Compute:

Variable Value
weeks 1
days 3

Full weeks contribution:

1 * 28 + 7 * (1 * 0 / 2)
= 28

Remaining contribution:

3 * (1 + 1) + 3 * 2 / 2
= 6 + 3
= 9

Final answer:

28 + 9 = 37

Deposits:

Day Deposit Running Total
1 1 1
2 2 3
3 3 6
4 4 10
5 5 15
6 6 21
7 7 28
8 2 30
9 3 33
10 4 37

Example 3

Input:

n = 20

Compute:

Variable Value
weeks 2
days 6

Full weeks contribution:

2 * 28 + 7 * (2 * 1 / 2)
= 56 + 7
= 63

Remaining contribution:

6 * (2 + 1) + 6 * 5 / 2
= 18 + 15
= 33

Final answer:

63 + 33 = 96

Deposits during the third week:

Day in Partial Week Deposit
Monday 3
Tuesday 4
Wednesday 5
Thursday 6
Friday 7
Saturday 8

Partial week total:

3 + 4 + 5 + 6 + 7 + 8 = 33

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only constant time arithmetic operations are used
Space O(1) No extra data structures are allocated

The algorithm performs a fixed number of arithmetic calculations regardless of the input size. No loops or auxiliary storage are required, so both time and space usage remain constant.

Test Cases

sol = Solution()

assert sol.totalMoney(1) == 1       # smallest input
assert sol.totalMoney(4) == 10      # partial first week
assert sol.totalMoney(7) == 28      # exactly one full week
assert sol.totalMoney(8) == 30      # start of second week
assert sol.totalMoney(10) == 37     # provided example
assert sol.totalMoney(14) == 63     # exactly two weeks
assert sol.totalMoney(20) == 96     # provided example
assert sol.totalMoney(21) == 105    # three complete weeks
assert sol.totalMoney(28) == 154    # four complete weeks
assert sol.totalMoney(1000) == 74926  # large constraint value
Test Why
n = 1 Validates smallest possible input
n = 4 Tests partial first week
n = 7 Tests exact one week boundary
n = 8 Tests transition into second week
n = 10 Validates provided example
n = 14 Tests exact multiple of two weeks
n = 20 Validates larger partial week example
n = 21 Tests three complete weeks
n = 28 Tests several full week transitions
n = 1000 Stress test for upper constraint

Edge Cases

One important edge case is when n is less than 7. In this situation, there are no complete weeks, only a partial first week. A buggy implementation might incorrectly assume at least one complete week exists. The current implementation handles this correctly because weeks = n // 7 becomes 0, and the entire answer is computed through the remaining days formula.

Another important edge case occurs when n is exactly divisible by 7. In this case, there are no leftover days. Many implementations make off by one mistakes here by accidentally adding deposits for an extra partial week. This implementation avoids that problem because days = n % 7 becomes 0, making the remaining contribution equal to zero automatically.

A third edge case involves transitions between weeks, such as n = 8 or n = 15. These inputs verify that the Monday starting value correctly increases each week. The implementation handles this by using weeks + 1 as the starting value for the partial week, ensuring the arithmetic progression starts at the correct amount.