Problem Statement
You are given an integer array daysLate, where daysLate[i] tells you how many days late the i-th book was returned.
The library charges a fee for each book:
Exactly 1 day late: charge 1.
Between 2 and 5 days late, including both limits: charge 2 × daysLate[i].
More than 5 days late: charge 3 × daysLate[i].
Return the total fee collected from all the books.
Example 1
Input: daysLate = [2, 4, 6]
Output: 30
Explanation: The first book is 2 days late, so the fee is 4 (2 × 2). The second book is 4 days late, so the fee is 8 (2 × 4). The third book is 6 days late, so the fee is 18 (3 × 6). Therefore, the total fee is 4 + 8 + 18 = 30.
Example 2
Input: daysLate = [1, 3, 5]
Output: 17
Explanation: The first book is 1 day late, so the fee is 1. The second book is 3 days late, so the fee is 6 (2 × 3). The third book is 5 days late, so the fee is 10 (2 × 5). Therefore, the total fee is 1 + 6 + 10 = 17.
Approach
Each book’s fee depends only on how many days late that book was returned. We can read the array from left to right, apply the matching rule, and add the fee to a running total.
After each book, totalPenalty holds the fees for every book checked so far. Once we reach the end of the array, it holds the answer.
The selected rate applies to all late days for that book. For example, a book returned 6 days late costs 3 × 6 = 18.
Algorithm
Initialize
totalPenaltyto0to store the combined penalty for all books.Traverse the
daysLatearray from the first element to the last. Letdaysrepresent the current book’s number of days late.If
days == 1, add1tototalPenalty.Otherwise, if
daysis between2and5inclusive, calculate the book’s penalty as2 * daysand add it tototalPenalty.Otherwise, if
days > 5, calculate the book’s penalty as3 * daysand add it tototalPenalty.If none of these conditions apply, leave
totalPenaltyunchanged for that book.After processing every book, return
totalPenalty.
Dry Run
Library Late Fee Calculator
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Calculates the total late fee across all returned books. int lateFee(vector<int>& daysLate) { // Stores the cumulative penalty across all books int totalPenalty = 0; // Iterate through each book's late day count for (int i = 0; i < daysLate.size(); i++) { int day = daysLate[i]; // Exactly one late day has its own fixed fee. if (day == 1) { totalPenalty += 1; } else if (day >= 2 && day <= 5) { // Both 2 and 5 belong to the double-rate range. totalPenalty += 2 * day; } else if (day > 5) { // The higher rate applies to every late day. totalPenalty += 3 * day; } } return totalPenalty; }};// Driver codeint main() { vector<int> daysLate = {2, 4, 6}; Solution sol; cout << sol.lateFee(daysLate) << '\n'; return 0;}Complexity Analysis
Time Complexity: O(N), where N is the number of books. The loop visits each book exactly once and calculates its late fee in constant time.
Space Complexity: O(1), as we don't use any extra space apart from a few variables.
Interview follow-up Questions
They contribute 0 to the total fee. Since days == 0 does not match any penalty condition (days == 1, 2 <= days <= 5, or days > 5), totalPenalty remains unchanged for that book.
Be the first to add a comment.