1716. Calculate Money in Leetcode Bank - Explanation

Problem Link



1. Simulation

class Solution:
    def totalMoney(self, n: int) -> int:
        day, deposit = 0, 1
        res = 0

        while day < n:
            res += deposit
            deposit += 1
            day += 1

            if day % 7 == 0:
                deposit = 1 + day // 7

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)

2. Math

class Solution:
    def totalMoney(self, n: int) -> int:
        weeks = n // 7
        low = 28
        high = 28 + 7 * (weeks - 1)
        res = weeks * (low + high) // 2

        monday = weeks + 1
        for i in range(n % 7):
            res += i + monday

        return res

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)

3. Math (Optimal)

class Solution:
    def totalMoney(self, n: int) -> int:
        SUM = lambda x: (x * (x + 1)) >> 1
        weeks = n // 7
        res = SUM(weeks - 1) * 7 + weeks * SUM(7)
        res += SUM(n % 7) + weeks * (n % 7)
        return res

Time & Space Complexity

  • Time complexity: O(1)O(1)
  • Space complexity: O(1)O(1)