1716. Calculate Money in Leetcode Bank
Model: qwen2.5-coder:14b
Topics: Math,Greedy
FAANG asked: 0
Acceptance rate: 65.4%
Problem Breakdown
Hercy wants to save money in a bank where he deposits an increasing amount each day. He starts with 1 each subsequent day until Sunday. Every new Monday, he starts again but with an increased base amount compared to the previous Monday. Given a number of days n, we need to calculate the total amount deposited in the bank at the end of the nth day.
Inputs:
- An integer
nrepresenting the number of days.
Outputs:
- An integer representing the total amount of money deposited in the bank after
ndays.
Implicit Constraints/Edge Cases:
- The input
nis always between 1 and 1000. - There are no negative numbers or zero, as the problem specifies that
nis at least 1. - The pattern repeats every week, so understanding the weekly cycle is crucial.
Intuition
A brute-force approach would involve simulating each day’s deposit by iterating through all days up to n, keeping track of the current day of the week and adjusting the deposit amount accordingly. This approach has a time complexity of O(n), which is acceptable given the constraints, but it might not be the most efficient.
The key insight is to recognize that the problem can be broken down into complete weeks and any remaining days. Each complete week follows a predictable pattern where the total deposit for a week starting with base amount b is (28 + 7*(b-1)). For example, the first week starts with 28, the second week starts with 35, and so on. The remaining days after complete weeks can be handled separately.
Approach
-
Calculate Complete Weeks:
- Determine how many complete weeks are in
ndays using integer division (n // 7). - Calculate the total amount deposited for these complete weeks using the formula for the sum of an arithmetic series.
- Determine how many complete weeks are in
-
Calculate Remaining Days:
- Determine the number of remaining days after accounting for complete weeks (
n % 7). - Calculate the total amount deposited for these remaining days, starting from the base amount of the next week.
- Determine the number of remaining days after accounting for complete weeks (
-
Combine Results:
- Sum the amounts from the complete weeks and the remaining days to get the final result.
Complexity Analysis
- Time Complexity: O(1) because all calculations are done in constant time regardless of
n. - Space Complexity: O(1) as no additional data structures are used that grow with input size.
Solution
def totalMoney(n):
# Calculate the number of complete weeks and remaining days
complete_weeks = n // 7
remaining_days = n % 7
# Total money from complete weeks
# Sum of arithmetic series: (number_of_terms / 2) * (first_term + last_term)
total_complete_weeks_money = (complete_weeks * (28 + 7 * (complete_weeks - 1))) // 2
# Base amount for the first day of the next week
base_amount_next_week = complete_weeks + 1
# Total money from remaining days
total_remaining_days_money = ((remaining_days * (2 * base_amount_next_week + remaining_days - 1)) // 2)
# Return the sum of both parts
return total_complete_weeks_money + total_remaining_days_money
# Example usage:
print(totalMoney(4)) # Output: 10
print(totalMoney(10)) # Output: 37
print(totalMoney(20)) # Output: 96
Edge Cases Handled
- Single Day (
n = 1): The function correctly calculates the deposit as $1. - Complete Week (
n = 7): The function calculates the total for one complete week, which is $28. - Multiple Complete Weeks (
n = 14): The function handles multiple weeks correctly, totaling $56. - Remaining Days After Complete Weeks (
n = 10): The function accounts for remaining days after complete weeks, totaling $37. - Maximum Input (
n = 1000): The function efficiently calculates the total for the maximum input size.