{x}
blog image

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 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

Solution Explanation

This problem involves calculating the total amount of money saved over a period of n days, following a specific pattern of savings. The pattern is:

  • Mondays: The amount saved increases by $1 each Monday compared to the previous Monday.
  • Other Days: The amount saved increases by $1 each day compared to the previous day.

The solution uses a mathematical approach to efficiently calculate the total sum without iterating through each day. It leverages the arithmetic series formula to compute the sum.

Approach

The solution breaks down the problem into two parts:

  1. Mondays: Calculate the total saved on all Mondays within the n days.
  2. Other Days: Calculate the total saved on all the non-Monday days.

The solution then sums these two amounts to get the final answer. The clever part is using integer division (/) and modulo operation (%) to efficiently determine the number of full weeks and the remaining days, thus simplifying the calculations.

Code Explanation (Python Example)

class Solution:
    def totalMoney(self, n: int) -> int:
        a, b = divmod(n, 7)  # a: number of full weeks, b: remaining days
        return (28 + 28 + 7 * (a - 1)) * a // 2 + (a * 2 + b + 1) * b // 2

  • a, b = divmod(n, 7): This line efficiently calculates the number of full weeks (a) and the remaining days (b) using Python's divmod function.

  • (28 + 28 + 7 * (a - 1)) * a // 2: This part calculates the total money saved on Mondays.

    • 28: The sum of money saved on Mondays in the first week (1+2+3+4+5+6+7) .
    • 28 + 7 * (a - 1): This calculates the sum of money saved on Mondays for all weeks after the first week (Arithmetic Progression).
    • * a // 2: This multiplies by the number of weeks and divides by 2 (arithmetic series formula).

  • (a * 2 + b + 1) * b // 2: This part calculates the total money saved on non-Monday days.

    • a * 2 + b + 1: This represents the average of the sum of money saved on non-Monday days.
    • * b // 2: This multiplies by the number of non-Monday days and divides by 2 (arithmetic series formula).

  • return ...: The final result is the sum of the total money saved on Mondays and non-Monday days.

Time and Space Complexity

  • Time Complexity: O(1) - The solution performs constant-time calculations regardless of the input size n.
  • Space Complexity: O(1) - The solution uses a constant amount of extra space.

The provided Java, C++, and Go codes follow the same logic and mathematical approach, differing only in syntax. They all achieve the same O(1) time and space complexity.