Calculate Money in Leetcode Bank

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 n<sup>th</sup> day.

For example:

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

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.

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.

Here's the solution to the LeetCode problem:

def totalMoney(n: int) -> int:
    weeks = n // 7
    days = n % 7
    
    total = 0
    
    # Calculate the total for the complete weeks
    total += weeks * (2 * 2 + (weeks - 1) * 1) * 7 // 2  # Sum of arithmetic series
    
    # Calculate the total for the remaining days
    for i in range(days):
        total += (weeks + 1 + i)
        
    return total

Explanation:

1. Calculate the number of complete weeks and remaining days:

   • weeks = n // 7 gives the number of full weeks.
   • days = n % 7 gives the remaining days.

2. Calculate the total amount for the complete weeks:

   • Each week forms an arithmetic series with a common difference of 1. The first week starts with $1, the second week starts with $2, and so on.
   • The sum of the amounts deposited during the complete weeks can be calculated using the formula for the sum of an arithmetic series.
   • Specifically, we sum the starting values of each week (1, 2, 3, ..., weeks) and apply the arithmetic series sum formula to the amount deposited each week.

3. Calculate the total amount for the remaining days:

   • For the remaining days, we iterate through each day and add the appropriate amount to the total.
   • The amount deposited each day is the starting amount for that week (weeks + 1) plus the day number (0 to days - 1).

4. Return the total amount.

Example:

If n = 20, then weeks = 2 and days = 6.

• The total amount for the complete weeks is:
  • Week 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28
  • Week 2: 2 + 3 + 4 + 5 + 6 + 7 + 8 = 35
  • Total for complete weeks: 28 + 35 = 63
• The total amount for the remaining days is:
  • 3 + 4 + 5 + 6 + 7 + 8 = 33
• The overall total amount is: 63 + 33 = 96

Big O Runtime Analysis:

The time complexity of this solution is O(1). The number of weeks and remaining days are calculated using division and modulo operations, which take constant time. The calculation of the total amount for the complete weeks involves arithmetic operations, which also take constant time. The loop for the remaining days iterates at most 6 times (since there can be at most 6 remaining days), which is also considered constant time. Therefore, the overall time complexity is O(1).

Big O Space Usage Analysis:

The space complexity of this solution is O(1). The algorithm uses a fixed number of variables (weeks, days, total) regardless of the input size. Therefore, the space required does not scale with the input, making it constant space complexity.