💬 Discord
Sign In
NeetCode #886LC-1716EasyMath & Geometry
← Back to All Problems

#886 · #1716 · Calculate Money in Leetcode Bank(计算力扣银行的钱)

📌 Problem Statement & Constraints

Hercy saves money every day. On Monday of the first week he saves 1, and each following day he saves one more than the previous day. On each Monday after the first week, he saves one more than on the previous Monday. Given n, return the total amount saved after n days. Constraints: 1 <= n <= 1000.

💡 Core Algorithmic Approaches

  1. Split n into full weeks and a remainder: weeks, days = divmod(n, 7).
  2. A full week starting at base s sums to 7 * s + 28, because it is the arithmetic series s+1, s+2, ..., s+7.
  3. Summing over weeks full weeks gives 28 * weeks + 7 * weeks * (weeks - 1) / 2, the second term accounting for the weekly increment.
  4. The partial week starts at base weeks, and its first days terms sum to days * (days + 1) / 2 + days * weeks.

💻 Benchmark Python3 Implementation

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks, days = divmod(n, 7)
        # full weeks: week k (0-indexed) starts at k, and 1+2+...+7 = 28
        full = 28 * weeks + 7 * weeks * (weeks - 1) // 2
        # partial week starts at base `weeks`
        rem = days * (days + 1) // 2 + days * weeks
        return full + rem

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1): closed-form arithmetic.
💾 Space Complexity
O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Simulating day by day: O(n) and unnecessary when a closed form exists.
  • Using 28 * weeks alone: the weekly base increases by one each week, contributing the triangular term.
  • Omitting the days * weeks offset: the partial week starts at base weeks, not at zero.
  • Using floating-point division for the triangular sums: integer division is exact and avoids rounding.