Scale Engineer

Calculate Money in Leetcode Bank

Easy
#1572Time: O(n) because the solution involves a single loop that runs `n` times.Space: O(1) as we only use a constant amount of extra space for variables like `total`, `week`, and `dayOfWeek`.
Patterns
Math

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate from day 1 to day n, calculating the deposit for each day and adding it to a running total. The amount deposited on any given day can be determined by its week number and its position within that week.

Algorithm

    1. Initialize a variable total to 0.
    1. Start a loop that iterates from day = 0 to n - 1.
    1. In each iteration, calculate the current week number: week = day / 7.
    1. Calculate the day within the week (0 for Monday, 1 for Tuesday, etc.): dayOfWeek = day % 7.
    1. The amount deposited on this day is (week + 1) + dayOfWeek. The (week + 1) part represents the base amount for that week's Monday.
    1. Add the calculated daily deposit to the total.
    1. After the loop finishes, return the final total.

Walkthrough

We can solve this by looping through each day from 1 to n. For each day, we need to figure out how much money Hercy deposits. The pattern of deposits repeats every week, with an increment. The deposit on any given day d (1-indexed) is (week_number) + (day_of_week). For a 0-indexed day i (from 0 to n-1), the deposit is (i / 7) + (i % 7) + 1. We can simply loop from day = 0 to n-1, calculate this value in each iteration, and add it to a running total.

class Solution {    public int totalMoney(int n) {        int total = 0;        for (int day = 0; day < n; day++) {            int week = day / 7;            int dayOfWeek = day % 7;            // The deposit is (week + 1) for Monday, plus (dayOfWeek)            int dailyDeposit = (week + 1) + dayOfWeek;            total += dailyDeposit;        }        return total;    }}

Complexity

Time

O(n) because the solution involves a single loop that runs `n` times.

Space

O(1) as we only use a constant amount of extra space for variables like `total`, `week`, and `dayOfWeek`.

Trade-offs

Pros

  • Very easy to understand and implement.

  • It's a direct translation of the problem statement into code.

Cons

  • Not the most performant solution, especially if n were much larger. Its runtime is directly proportional to the input n.

Solutions

class Solution { public int totalMoney ( int n ) { int a = n / 7 , b = n % 7 ; return ( 28 + 28 + 7 * ( a - 1 )) * a / 2 + ( a * 2 + b + 1 ) * b / 2 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem