Difficulty: Easy | Acceptance: 82.40% | Paid: No Topics: Math
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-th day.
- Examples
- Constraints
- Simulation Approach
- Mathematical Formula
Examples
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 puts in only $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
Simulation Approach
Intuition Iterate through each day, calculate the amount saved on that day based on the week and day of week, and accumulate the total.
Steps
- Initialize total to 0
- For each day from 1 to n:
- Calculate the week number (0-indexed) as (day - 1) // 7
- Calculate the day of week (0-indexed) as (day - 1) % 7
- Amount saved = week + day_of_week + 1
- Add to total
- Return total
class Solution:
def totalMoney(self, n: int) -> int:
total = 0
for day in range(1, n + 1):
week = (day - 1) // 7
day_of_week = (day - 1) % 7
total += week + day_of_week + 1
return total
Complexity
- Time: O(n)
- Space: O(1)
- Notes: Simple and intuitive, but not optimal for very large n values.
Mathematical Formula
Intuition Use arithmetic series formulas to calculate the sum of complete weeks and remaining days separately, avoiding iteration.
Steps
- Calculate complete weeks w = n // 7 and remaining days r = n % 7
- Sum of complete weeks = 28w + 7 × w × (w - 1) / 2
- Sum of remaining days = r × w + r × (r + 1) / 2
- Return the sum of both parts
class Solution:
def totalMoney(self, n: int) -> int:
w = n // 7
r = n % 7
complete_weeks = 28 * w + 7 * w * (w - 1) // 2
remaining_days = r * w + r * (r + 1) // 2
return complete_weeks + remaining_days
Complexity
- Time: O(1)
- Space: O(1)
- Notes: Optimal solution with constant time complexity using mathematical derivation.