# Calculate Money in Leetcode Bank
**Difficulty:** EASY
[External](https://leetcode.com/problems/calculate-money-in-leetcode-bank)
Canonical: https://scaleengineer.com/dsa/problems/calculate-money-in-leetcode-bank
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
---
## Problem
Hercy wants to save money for his first car. He puts money in the Leetcode bank **every day**.

He starts by putting in `$1` on Monday, the first day. Every day from Tuesday to Sunday, he will put in `$1` more than the day before. On every subsequent Monday, he will put in `$1` more than the **previous Monday**. 

Given `n`, return _the total amount of money he will have in the Leetcode bank at the end of the_ `nth` _day._

**Example 1:**

**Input:** n = 4
**Output:** 10
**Explanation:** After the 4th day, the total is 1 + 2 + 3 + 4 = 10.

**Example 2:**

**Input:** n = 10
**Output:** 37
**Explanation:** 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
**Explanation:** 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`

# Approaches
## Iterative Simulation
This approach directly simulates the process described in the problem. We iterate from day 1 to day `n`, calculating the deposit for each day and adding it to a running total. The amount deposited on any given day can be determined by its week number and its position within that week.
**Time:** O(n) because the solution involves a single loop that runs `n` times. · **Space:** O(1) as we only use a constant amount of extra space for variables like `total`, `week`, and `dayOfWeek`.
**Pros:** Very easy to understand and implement.; It's a direct translation of the problem statement into code.
**Cons:** Not the most performant solution, especially if `n` were much larger. Its runtime is directly proportional to the input `n`.
### Explanation
We can solve this by looping through each day from 1 to `n`. For each day, we need to figure out how much money Hercy deposits. The pattern of deposits repeats every week, with an increment. The deposit on any given day `d` (1-indexed) is `(week_number) + (day_of_week)`. For a 0-indexed day `i` (from 0 to n-1), the deposit is `(i / 7) + (i % 7) + 1`. We can simply loop from `day = 0` to `n-1`, calculate this value in each iteration, and add it to a running total.

```java
class Solution {
    public int totalMoney(int n) {
        int total = 0;
        for (int day = 0; day < n; day++) {
            int week = day / 7;
            int dayOfWeek = day % 7;
            // The deposit is (week + 1) for Monday, plus (dayOfWeek)
            int dailyDeposit = (week + 1) + dayOfWeek;
            total += dailyDeposit;
        }
        return total;
    }
}
```
### Algorithm
- 1. Initialize a variable `total` to 0.
- 2. Start a loop that iterates from `day = 0` to `n - 1`.
- 3. In each iteration, calculate the current week number: `week = day / 7`.
- 4. Calculate the day within the week (0 for Monday, 1 for Tuesday, etc.): `dayOfWeek = day % 7`.
- 5. The amount deposited on this day is `(week + 1) + dayOfWeek`. The `(week + 1)` part represents the base amount for that week's Monday.
- 6. Add the calculated daily deposit to the `total`.
- 7. After the loop finishes, return the final `total`.

## Arithmetic Progression Formula
A more optimized approach involves using mathematical formulas to calculate the total sum in constant time, avoiding the need for a loop. We can decompose the total number of days `n` into a number of full weeks and a number of remaining days. We then calculate the sum for the full weeks and the sum for the remaining days separately and add them together.
**Time:** O(1) because the calculation involves a fixed number of arithmetic operations, regardless of the value of `n`. · **Space:** O(1) as we only use a few variables to store intermediate calculations.
**Pros:** Extremely efficient, providing a constant-time solution.; It's the optimal way to solve the problem.
**Cons:** Requires mathematical reasoning to derive the formulas, making it slightly more complex to come up with than the direct simulation.
### Explanation
First, we determine the number of complete 7-day weeks (`num_weeks = n / 7`) and the number of days left in the final, potentially incomplete week (`remaining_days = n % 7`).

**Sum for Full Weeks:** The money saved in the first week is `1+2+...+7 = 28`. The money saved in the second week is `2+3+...+8 = 35`. The sums of money for each full week form an arithmetic progression: 28, 35, 42, ... with a common difference of 7. We can use the formula for the sum of an arithmetic series, `S_k = k/2 * (2a + (k-1)d)`, where `k` is `num_weeks`, `a` is 28, and `d` is 7.

**Sum for Remaining Days:** For the leftover days, the saving starts with an amount of `num_weeks + 1` on the Monday of that week. The amounts for the `remaining_days` also form an arithmetic progression. We can again use the arithmetic series sum formula to calculate this part.

The final answer is the sum of these two parts.

```java
class Solution {
    public int totalMoney(int n) {
        int numWeeks = n / 7;
        int remainingDays = n % 7;

        // Sum of money for all the full weeks
        // This is an AP: 28, 35, 42, ...
        // Sum of AP = k/2 * (2*a + (k-1)*d)
        // Here, k = numWeeks, a = 28, d = 7
        int fullWeeksSum = numWeeks * 28 + 7 * numWeeks * (numWeeks - 1) / 2;

        // Sum of money for the remaining days in the last week
        // The starting deposit for the last week is (numWeeks + 1)
        int mondayDeposit = numWeeks + 1;
        int remainingSum = 0;
        for (int i = 0; i < remainingDays; i++) {
            remainingSum += mondayDeposit + i;
        }

        return fullWeeksSum + remainingSum;
    }
}
```
### Algorithm
- 1. Calculate the number of full weeks: `num_weeks = n / 7`.
- 2. Calculate the number of remaining days: `remaining_days = n % 7`.
- 3. Calculate the total money from the full weeks. The sum for week `k` (1-indexed) is `28 + 7 * (k-1)`. The total sum for `num_weeks` is the sum of this arithmetic progression: `total_full_weeks = num_weeks * 28 + 7 * num_weeks * (num_weeks - 1) / 2`.
- 4. Calculate the total money from the remaining days. The deposit on the first day of this last week is `num_weeks + 1`. The sum for `remaining_days` is another arithmetic progression: `total_remaining = remaining_days * (num_weeks + 1) + remaining_days * (remaining_days - 1) / 2`.
- 5. The final result is `total_full_weeks + total_remaining`.

# Solutions
### Java

```java
class Solution { public int totalMoney ( int n ) { int a = n / 7 , b = n % 7 ; return ( 28 + 28 + 7 * ( a - 1 )) * a / 2 + ( a * 2 + b + 1 ) * b / 2 ; } }
```

### CPP

```cpp
class Solution { public: int totalMoney ( int n ) { int a = n / 7 , b = n % 7 ; return ( 28 + 28 + 7 * ( a - 1 )) * a / 2 + ( a * 2 + b + 1 ) * b / 2 ; } };
```

### Python

```python
class Solution : def totalMoney ( self , n : int ) -> int : a , b = divmod ( n , 7 ) return ( 28 + 28 + 7 * ( a - 1 )) * a // 2 + ( a * 2 + b + 1 ) * b // 2
```