Code Implementation

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7
        days = n % 7
        # Money from complete weeks: sum of arithmetic progression
        # Each week starts with 1 more than previous week
        total = 0
        # For complete weeks
        total += 7 * weeks * (weeks + 1) // 2
        # For leftover days in the last (possibly incomplete) week
        total += days * (weeks + 1) + days * (days - 1) // 2
        return total
      

class Solution {
public:
    int totalMoney(int n) {
        int weeks = n / 7;
        int days = n % 7;
        int total = 0;
        // Complete weeks
        total += 7 * weeks * (weeks + 1) / 2;
        // Remaining days
        total += days * (weeks + 1) + days * (days - 1) / 2;
        return total;
    }
};
      

class Solution {
    public int totalMoney(int n) {
        int weeks = n / 7;
        int days = n % 7;
        int total = 0;
        // Complete weeks
        total += 7 * weeks * (weeks + 1) / 2;
        // Remaining days
        total += days * (weeks + 1) + days * (days - 1) / 2;
        return total;
    }
}
      

var totalMoney = function(n) {
    const weeks = Math.floor(n / 7);
    const days = n % 7;
    let total = 0;
    // Complete weeks
    total += 7 * weeks * (weeks + 1) / 2;
    // Remaining days
    total += days * (weeks + 1) + days * (days - 1) / 2;
    return total;
};
      

Problem Description

You are given an integer n representing the number of days. Each day, you deposit money into the Leetcode bank according to the following rules:

• On the first day of every week (Monday), you deposit $1. Each subsequent day of the week, you deposit $1 more than the previous day.
• At the start of each new week, the deposit amount for Monday increases by $1 compared to the previous week.
• For example, on the first Monday you deposit $1, Tuesday $2, ..., Sunday $7. The next Monday you deposit $2, Tuesday $3, etc.

Your task is to return the total amount of money in the bank after n days.

Constraints:

• 1 <= n <= 1000

Thought Process

The problem requires calculating the total deposits over n days, where the deposit pattern increases both weekly and daily. At first glance, it might seem natural to simulate each day and sum the deposits. However, this would be inefficient for larger values of n.

Instead, we can look for patterns. Noticing that each week starts with a higher base deposit and daily increases, we realize that each week forms an arithmetic progression. By breaking the problem into complete weeks and leftover days, we can use formulas to compute the sums efficiently.

The shift from brute-force simulation to mathematical calculation is key for optimization.

Solution Approach

• Step 1: Divide Days into Weeks and Days
  • Let weeks = n // 7 (integer division) be the number of complete weeks.
  • Let days = n % 7 be the number of leftover days in the last (possibly incomplete) week.
• Step 2: Calculate Sums for Complete Weeks
  • For each complete week, the Monday deposit increases by 1 each week. The total for week i (starting from 0) is the sum of an arithmetic progression: sum = 7 * (i + 1) + 21, but more generally, the sum for week i is 7 * (i + 1) + 21.
  • However, we can use the formula for the sum of the first n natural numbers, and sum over all weeks: 7 * weeks * (weeks + 1) / 2.
• Step 3: Calculate Sums for Remaining Days
  • The leftover days start from the next Monday value (weeks + 1), and increase by 1 each day.
  • The sum for these days is: days * (weeks + 1) + days * (days - 1) / 2.
• Step 4: Add Both Parts
  • The total is the sum of the complete weeks and the remaining days.
• Step 5: Return the Total
  • Return the computed value as the answer.

Example Walkthrough

Let's consider n = 10:

• Step 1: weeks = 10 // 7 = 1, days = 10 % 7 = 3
• Step 2: For the first complete week:
  • Deposits: 1, 2, 3, 4, 5, 6, 7 (sum = 28)
• Step 3: For the remaining 3 days (Monday, Tuesday, Wednesday of next week):
  • Deposits: 2, 3, 4 (sum = 9)
• Step 4: Total = 28 (week) + 9 (days) = 37

So, after 10 days, the total money in the bank is 37.

Time and Space Complexity

• Brute-force Approach:
  • Iterate through each day, update deposit, and accumulate total.
  • Time Complexity: O(n) because we loop through every day.
  • Space Complexity: O(1) since only a few variables are used.
• Optimized Approach (Current):
  • We use constant-time arithmetic calculations.
  • Time Complexity: O(1) because all operations are simple arithmetic.
  • Space Complexity: O(1) as only a fixed number of variables are used.

Summary

The "Calculate Money in Leetcode Bank" problem can be elegantly solved by recognizing the arithmetic progression in the deposit pattern. Instead of simulating each day, we break the problem into complete weeks and leftover days, and use formulas to calculate the sums directly. This reduces the time complexity from O(n) to O(1), making the solution both efficient and clean.

The key insight is to leverage mathematical patterns and formulas for summing sequences, which is a powerful technique for many similar problems.