Topic describes

This is 1716 on LeetCode. The difficulty of calculating the money deducted from the bank is simple.

Tag: “math”, “simulation”

Hercy wants to save money to buy his first car. He tried to deposit money in the bank every day.

At first, he deposited one dollar on Monday. From Tuesday through Sunday, he deposited a dollar more each day than the day before. Each following Monday, he deposited one more dollar than the Monday before.

I’m going to give you n, and I’m going to ask you to go back to the total amount of dollars he had at the bank at the end of day N.

Example 1:

Input: n = 4 Output: 10 Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.Copy the code

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 second Monday, Hercy deposits 2 dollars.Copy the code

Example 3:

Input: n = 20 Output: 96 On day 20, the total was (1 + 2 + 3 + 4 + 5 + 6 + 7 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.Copy the code

Tip:


  • 1 < = n < = 1000 1 <= n <= 1000

simulation

According to the meaning of the question, the simulation can be divided into two steps for calculation.

Calculate the whole week first: total a=⌊n7⌋a = \left \lfloor \frac{n}{7} \right \rfloora=⌊7n⌋ weeks, the initial amount of the first week is 111, the amount of the initial day of each week increases by 111, the amount of the week can be directly solved by using the “arithmetic summation” formula.

Then calculate the amount of the last week (if any) : total b= N (mod7)b =n \ pMOD 7b= N (mod7) days, use the sum of the immediately following starting day to continue to add up.

Code:

class Solution {
    public int totalMoney(int n) {
        int a = n / 7, b = n % 7;
        int ans = 0, k = 1;
        while (a-- > 0) {
            ans += (k + (k + 6)) * 7 / 2;
            k++;
        }
        while (b-- > 0) ans += k++;
        returnans; }}Copy the code
  • O(a+b)O(a +b)O(a +b)
  • Space complexity: O(1)O(1)O(1)

(Optimization) simulation

Furthermore, the sum of the starting day of each complete week is 111 more than the sum of the starting day of the last week, and the sum of the daily amount within the week increases by 111. Therefore, the sum of the sum of the adjacent complete weeks also meets the “equal difference” nature, and the “equal difference sequence summation” formula O(1)O(1)O(1) O(1) can be directly used to solve the sum of the sum of the whole week. The same applies to the amount of the following week (if any).

Code:

class Solution {
    public int totalMoney(int n) {
        int a = n / 7, b = n % 7;
        int a1 = (1 + 7) * 7 / 2, an = (a + (a + 6)) * 7 / 2;
        int s1 = (a1 + an) * a / 2;
        a++;
        int s2 = (a + (a + b - 1)) * b / 2;
        returns1 + s2; }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.1716 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode by the start date, some of which are locked.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.