Calculate Money in Leetcode Bank

How it works

We can derive a closed-form formula using the sum of first k natural numbers: SUM(k) = k*(k+1)/2. Each week's extra contribution above the base week follows a pattern, and the remaining days also follow an arithmetic progression. This eliminates the loop needed for remaining days in the previous approach.

Steps

1. Define a helper function SUM(x) = x*(x+1)/2 which gives the sum of first x natural numbers.
2. Calculate the number of complete weeks.
3. The contribution from complete weeks is: SUM(weeks-1) * 7 + weeks * SUM(7). This accounts for the increasing weekly base and the standard week pattern.
4. The contribution from remaining days is: SUM(n % 7) + weeks * (n % 7). This adds the base daily progression plus the offset from the current week.
5. Return the total sum.

Complexity

• Time complexity: O(1)
• Space complexity: O(1)

Things to watch for

Using Wrong Starting Deposit for Each Week

Each Monday starts with week_number dollars (week 1 starts with 1, week 2 starts with 2, etc.), not always 1. Forgetting to increment the Monday deposit each week gives incorrect totals.

Off-by-One in Week Calculation

When computing complete weeks, using (n + 6) // 7 instead of n // 7 overcounts partial weeks as complete, leading to incorrect sums in the math-based approach.

class Solution:
    def totalMoney(self, n: int) -> int:
        SUM = lambda x: (x * (x + 1)) >> 1
        weeks = n // 7
        res = SUM(weeks - 1) * 7 + weeks * SUM(7)
        res += SUM(n % 7) + weeks * (n % 7)
        return res

class Solution {
public:
    int totalMoney(int n) {
        auto SUM = [](int x) { return (x * (x + 1)) / 2; };

        int weeks = n / 7;
        int res = SUM(weeks - 1) * 7 + weeks * SUM(7);
        res += SUM(n % 7) + weeks * (n % 7);
        return res;
    }
};