Problem Description

Hercy is saving money following a specific pattern. He deposits money into his bank account every day according to these rules:

Week 1:

• Monday: $1
• Tuesday: $2
• Wednesday: $3
• Thursday: $4
• Friday: $5
• Saturday: $6
• Sunday: $7

Week 2:

• Monday: $2 (previous Monday +$1)
• Tuesday: $3
• Wednesday: $4
• Thursday: $5
• Friday: $6
• Saturday: $7
• Sunday: $8

Pattern: Each week starts on Monday with $1 more than the previous week's Monday. Within each week, the amount increases by$1 each day from Monday to Sunday.

Given an integer n representing the number of days, calculate the total amount of money Hercy will have saved after n days.

Example walkthrough:

• If n = 10, this covers 1 full week plus 3 days into the second week
• Week 1: $1 +$2 + $3 +$4 + $5 +$6 + $7 =$28
• Week 2 (first 3 days): $2 +$3 + $4 =$9
• Total: $28 +$9 = $37

The solution uses mathematical formulas to calculate:

1. The sum for complete weeks using the arithmetic progression formula
2. The sum for any remaining partial week
3. The formula (28 + 28 + 7 * (a - 1)) * a // 2 calculates the total for a complete weeks
4. The formula (a * 2 + b + 1) * b // 2 calculates the total for the remaining b days

Intuition

Let's first observe the deposit pattern more carefully. If we look at complete weeks:

• Week 1: 1, 2, 3, 4, 5, 6, 7 (total = 28)
• Week 2: 2, 3, 4, 5, 6, 7, 8 (total = 35)
• Week 3: 3, 4, 5, 6, 7, 8, 9 (total = 42)

Notice that each complete week's total increases by 7 from the previous week. This forms an arithmetic sequence: 28, 35, 42, 49, ...

For a complete weeks, we need the sum of this arithmetic sequence. Using the arithmetic series formula sum = (first_term + last_term) * count / 2:

• First week total: 28
• Last (a-th) week total: 28 + 7 * (a - 1)
• Sum of a weeks: (28 + 28 + 7 * (a - 1)) * a / 2

Now for the remaining b days (where n = 7 * a + b), these days start from week (a + 1):

• The Monday of week (a + 1) would have deposit: a + 1
• The pattern for b days would be: (a + 1), (a + 2), (a + 3), ..., (a + b)

This is another arithmetic sequence with:

• First term: a + 1
• Last term: a + b
• Sum: ((a + 1) + (a + b)) * b / 2 = (2a + b + 1) * b / 2

By dividing n by 7 using divmod(n, 7), we get:

• a = number of complete weeks
• b = remaining days

The total money is simply the sum of money from complete weeks plus money from remaining days.

Learn more about Math patterns.

Solution Approach

The implementation uses a mathematical approach to directly calculate the total money without simulating day-by-day deposits.

Step 1: Divide the days into complete weeks and remaining days

a, b = divmod(n, 7)

• a represents the number of complete weeks
• b represents the remaining days (0 to 6)

Step 2: Calculate the sum for complete weeks

The formula (28 + 28 + 7 * (a - 1)) * a // 2 calculates the total for all complete weeks:

• Each complete week forms an arithmetic sequence: 28, 35, 42, ...
• First term: 28
• Last term: 28 + 7 * (a - 1)
• Using the arithmetic series sum formula: sum = (first + last) * count / 2
• This gives us: (28 + 28 + 7 * (a - 1)) * a // 2

Step 3: Calculate the sum for remaining days

The formula (a * 2 + b + 1) * b // 2 calculates the total for the partial week:

• The remaining b days start from week (a + 1)
• Monday of week (a + 1) has deposit: a + 1
• The deposits form the sequence: (a + 1), (a + 2), ..., (a + b)
• First term: a + 1
• Last term: a + b
• Sum: ((a + 1) + (a + b)) * b / 2 = (2a + b + 1) * b / 2

Step 4: Return the total

return (28 + 28 + 7 * (a - 1)) * a // 2 + (a * 2 + b + 1) * b // 2

The final answer is the sum of money from complete weeks plus money from the remaining partial week. The use of integer division // ensures the result is an integer.

Time Complexity: O(1) - Only arithmetic operations are performed
Space Complexity: O(1) - Only a constant amount of extra space is used

Example Walkthrough

Let's walk through the solution with n = 17 days.

Step 1: Divide into complete weeks and remaining days

a, b = divmod(17, 7)  # a = 2, b = 3

So we have 2 complete weeks and 3 remaining days.

Step 2: Calculate money from complete weeks

Week 1 deposits: 1, 2, 3, 4, 5, 6, 7 → Total = 28 Week 2 deposits: 2, 3, 4, 5, 6, 7, 8 → Total = 35

Using our formula for complete weeks:

(28 + 28 + 7 * (a - 1)) * a // 2
= (28 + 28 + 7 * (2 - 1)) * 2 // 2
= (28 + 28 + 7) * 2 // 2
= 63 * 2 // 2
= 63

We can verify: 28 + 35 = 63 ✓

Step 3: Calculate money from remaining 3 days

The 3 remaining days are in week 3:

• Day 15 (Monday of week 3): $3
• Day 16 (Tuesday of week 3): $4
• Day 17 (Wednesday of week 3): $5

Using our formula for remaining days:

(a * 2 + b + 1) * b // 2
= (2 * 2 + 3 + 1) * 3 // 2
= 8 * 3 // 2
= 24 // 2
= 12

We can verify: 3 + 4 + 5 = 12 ✓

Step 4: Calculate total

Total = 63 + 12 = 75

Therefore, after 17 days, Hercy will have saved $75.

Solution Implementation

Time and Space Complexity

Time Complexity: O(1)

The code performs a fixed number of arithmetic operations regardless of the input size n:

• One division with remainder operation (divmod)
• A constant number of arithmetic operations (additions, subtractions, multiplications, divisions)
• No loops or recursive calls

All operations execute in constant time, making the overall time complexity O(1).

Space Complexity: O(1)

The code uses only a fixed amount of extra space:

• Two variables a and b to store the quotient and remainder from divmod(n, 7)
• No additional data structures that grow with input size
• No recursive calls that would use stack space

The space usage remains constant regardless of the value of n, resulting in O(1) space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Week Calculation

A common mistake is incorrectly calculating the starting amount for each week. Students often think week k starts with amount k instead of k+1 for the Monday deposit.

Incorrect assumption:

• Week 1 Monday: $0
• Week 2 Monday: $1
• Week 3 Monday: $2

Correct pattern:

• Week 1 Monday: $1
• Week 2 Monday: $2
• Week 3 Monday: $3

Solution: Remember that week numbering starts at 1, and Monday of week w has deposit amount w.

2. Mishandling Edge Cases

When n = 7 (exactly one week) or when there are no remaining days (b = 0), the formula for remaining days should correctly evaluate to 0.

Potential issue: Division by zero or incorrect calculation when remaining_days = 0.

Solution: The formula (a * 2 + b + 1) * b // 2 naturally handles this case since when b = 0, the entire expression becomes 0 regardless of the value of a.

3. Integer Overflow in Other Languages

While Python handles arbitrary precision integers, in languages like Java or C++, the multiplication in the formula could cause overflow for large values of n.

Example: (28 + 28 + 7 * (a - 1)) * a could overflow before division.

Solution:

• Use appropriate data types (e.g., long long in C++)
• Rearrange the formula to perform division earlier if possible
• Consider modular arithmetic if the problem requires it

4. Incorrect Arithmetic Sequence Formula Application

Students might incorrectly apply the arithmetic sequence sum formula by:

• Forgetting to account for the changing starting point each week
• Using wrong first/last terms in the sequence

Common mistake:

# Incorrect: Assuming each week always sums to 28
total_from_complete_weeks = 28 * complete_weeks

Solution: Recognize that each complete week forms a different arithmetic sequence with sum increasing by 7 each week: 28, 35, 42, ...

5. Confusion Between Week Number and Array Indexing

When thinking about "week a+1", it's easy to confuse:

• Human-readable week numbers (1, 2, 3, ...)
• Zero-based indexing often used in programming

Solution: Stay consistent with the problem's convention where the first week is "Week 1" and Monday of Week 1 has deposit $1.