1904. The Number of Full Rounds You Have Played
Problem Description
The aim of the given problem is to compute the number of complete chess rounds played in an online tournament based on the login and logout times provided. Chess rounds commence every 15 minutes, starting from 00:00
and then at 00:15
, 00:30
, 00:45
, and so on until 23:45
. When a user logs in and logs out, we want to determine how many of these 15-minute rounds have fully passed.
- A
loginTime
is given which represents the time the user logs in to the game. - A
logoutTime
is also provided, which represents the time the user logs out of the game. - If the
logoutTime
is earlier thanloginTime
, this suggests the user played fromloginTime
through midnight to the next day, untillogoutTime
.
A single chess round is counted only if the user is logged in for the entire duration of the 15-minute round. The task is to calculate the number of such complete rounds played.
For example, if the loginTime
is 00:00
and logoutTime
is 00:30
, even though the user has been online for 30 minutes, they have played only 2 full rounds (00:00
and 00:15
), because they logout before the round starting at 00:30
could complete.
Intuition
The solution approach involves a series of steps to compute the total number of complete rounds:
-
Convert both
loginTime
andlogoutTime
to minutes. This simplification is done because working with minutes is easier than working with hours and minutes separately. It also helps to compare and perform arithmetic operations on the times effectively. -
Account for the scenario when
logoutTime
is earlier thanloginTime
. This indicates that the user played through midnight. To manage this, 24 hours (1440 minutes) are added tologoutTime
to properly calculate the number of rounds. -
Rounds are started every 15 minutes, but we are only interested in complete rounds. Therefore, for the
loginTime
that is in-between rounds, we need to round it up to the next round start time. On the other side, for thelogoutTime
, we need to round it down to the closest round start time that has been completed. -
Finally, the total number of complete rounds is the difference between the rounded times, divided by 15 (since each round is 15 minutes). We need to make sure not to count negative values in case
logoutTime
is right afterloginTime
, hence, we usemax(0, finish - start)
.
By rounding the loginTime
and logoutTime
to the closest round boundaries and then calculating the difference, we ensure that we're only counting the complete chess rounds.
The code provided is a direct translation of this intuition. It uses simple arithmetic operations and logical reasoning to find the solution without additional data structures or complicated algorithms, ensuring an efficient and clear solution to the problem.
Learn more about Math patterns.
Solution Approach
The solution's implementation follows a direct and methodical approach, utilizing the built-in functions of the coding language and basic arithmetic. Here's how the algorithm unfolds:
-
A helper function named
get
is defined, which takes a strings
representing time in the format "HH:MM" and converts this to the total number of minutes. It does so by multiplying the first two characters (hours) by 60 and adding to the last two characters (minutes), both of which are converted to integers. -
The
startTime
andfinishTime
are then converted to minutes using the helper functionget
. -
We then check if the
startTime
is greater than thefinishTime
. If it is, it means the player has played overnight, and therefore we add 24 hours (1440 minutes) to thefinishTime
. -
Next, we handle the round start and end times. For the
startTime
(now in minutes), we round up to the nearest round start time by adding 14 minutes before dividing by 15 and multiplying by 15. This is because if the player logs in at any time within a round (e.g.,00:07
or00:14
), they miss that round and can only start playing in the next one. The division and multiplication discard the remainder if any, effectively rounding up to the next multiple of 15. -
For the
finishTime
, we round down to the last complete round by simply dividing by 15. This is because if the player logs out anytime during a round, that round does not count as it is not completed. -
The difference between the finish and start values gives us the total number of rounds. But, we must ensure that this number is not negative, which is possible if the
finishTime
immediately follows thestartTime
. We usemax(0, finish - start)
to account for this, ensuring that the minimum number of rounds returned is zero.
The combination of helper function, careful addition for overnight sessions, and rounding the times to the nearest round boundaries are crucial in this implementation. There's no need for complex data structures; the entire solution leverages arithmetic operations to calculate the desired result.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach. Assume the following login and logout times:
loginTime
:22:47
logoutTime
:01:12
Following the steps of the solution:
-
Convert
loginTime
andlogoutTime
to minutes:get("22:47")
would result in22 * 60 + 47 = 1367
minutes.get("01:12")
would result in1 * 60 + 12 = 72
minutes.
-
Since
logoutTime
is on the next day (01:12 is after midnight), we add 1440 minutes (a full day) tologoutTime
to get the correct duration:- Updated
logoutTime
in minutes:72 + 1440 = 1512
minutes.
- Updated
-
Round the times to the nearest chess round start times:
- For
loginTime
, rounded up to the next round:(1367 + 14) / 15 * 15 = 1380
minutes. (This corresponds to the round that starts at 23:00.) - For
logoutTime
, rounded down to the last complete round:1512 / 15 * 15 = 1510
minutes. (This corresponds to the round that starts at 01:00.)
- For
-
Calculate the difference in rounded times and convert to the number of complete rounds:
- Difference in minutes:
1510 - 1380 = 130
minutes. - Number of complete rounds:
130 / 15 = 8
full rounds.
- Difference in minutes:
So, between 22:47
and 01:12
the next day, the user has played 8 complete chess rounds. We arrived at this conclusion by converting the given times into minutes, adjusting for overnight play, rounding the times to the nearest round boundaries, and computing the difference. This example cleanly demonstrates the efficiency of the solution approach in evaluating the number of complete rounds.
Solution Implementation
1class Solution:
2 def number_of_rounds(self, start_time: str, finish_time: str) -> int:
3 # Define a function to convert time from "HH:MM" format to minutes
4 def convert_to_minutes(time_str: str) -> int:
5 hours = int(time_str[:2]) # Extract hours and convert to integer
6 minutes = int(time_str[3:]) # Extract minutes and convert to integer
7 return hours * 60 + minutes # Return total minutes
8
9 # Convert start and finish times to minutes
10 start_minutes = convert_to_minutes(start_time)
11 finish_minutes = convert_to_minutes(finish_time)
12
13 # If start time is after finish time, assume finish time is the next day
14 if start_minutes > finish_minutes:
15 finish_minutes += 24 * 60 # Add 24 hours in minutes
16
17 # Round start time up to the next 15-minute mark
18 # and round finish time down to the previous 15-minute mark
19 # The 14 is added before division to ensure proper rounding up for start time
20 start_minutes_rounded = (start_minutes + 14) // 15
21 finish_minutes_rounded = finish_minutes // 15
22
23 # Calculate the number of complete 15-minute rounds
24 # Ensure that it's not negative by using max(0, ...)
25 complete_rounds = max(0, finish_minutes_rounded - start_minutes_rounded)
26
27 return complete_rounds
28
1class Solution {
2 // Method to calculate the number of rounds played, given a start and finish time.
3 public int numberOfRounds(String startTime, String finishTime) {
4 // Convert start and finish times to minutes
5 int startInMinutes = convertToMinutes(startTime);
6 int finishInMinutes = convertToMinutes(finishTime);
7
8 // If the finish time is less than the start time, it indicates the game went past midnight.
9 if (startInMinutes > finishInMinutes) {
10 finishInMinutes += 24 * 60; // Add 24 hours (in minutes) to the finish time to handle overnight duration
11 }
12
13 // The start time is rounded up to the next 15-minute mark, and the finish time is rounded down.
14 startInMinutes = (startInMinutes + 14) / 15 * 15;
15 finishInMinutes = (finishInMinutes / 15) * 15;
16
17 // Calculate the difference in 15-minute rounds and return the maximum of 0 or the computed rounds.
18 return Math.max(0, finishInMinutes / 15 - startInMinutes / 15);
19 }
20
21 // Helper method to convert a time String "HH:MM" to minutes.
22 private int convertToMinutes(String time) {
23 // Parse the hours and minutes from the time String and convert to minutes
24 int hours = Integer.parseInt(time.substring(0, 2));
25 int minutes = Integer.parseInt(time.substring(3));
26 return hours * 60 + minutes;
27 }
28}
29
1class Solution {
2public:
3 // Calculates the number of full rounds that can be played between the start and finish times
4 int numberOfRounds(string startTime, string finishTime) {
5 // Convert start and finish times to minutes
6 int startMinutes = convertToMinutes(startTime);
7 int finishMinutes = convertToMinutes(finishTime);
8
9 // If the finish time is less than the start time, it means the finish time is on the next day
10 if (startMinutes > finishMinutes) {
11 finishMinutes += 24 * 60; // Add 24 hours in minutes to the finish time
12 }
13
14 // Rounds start time to the next quarter hour if not already rounded
15 startMinutes = (startMinutes + 14) / 15 * 15;
16 // Rounds finish time down to the previous quarter hour
17 finishMinutes = finishMinutes / 15 * 15;
18
19 // Calculate the difference in the number of quarter hours played
20 // and ensure the result is not negative
21 return max(0, (finishMinutes - startMinutes) / 15);
22 }
23
24private:
25 // Helper function to convert time in "HH:MM" format to total number of minutes
26 int convertToMinutes(const string& time) {
27 int hours, minutes;
28 sscanf(time.c_str(), "%d:%d", &hours, &minutes); // Parse the string for hours and minutes
29 return hours * 60 + minutes; // Convert time to minutes
30 }
31};
32
1/**
2 * Helper function to convert a time string to its equivalent total minutes.
3 * @param {string} time - Time in the format of "HH:MM".
4 * @returns {number} Numeric representation of time in minutes.
5 */
6function toMinutes(time: string): number {
7 // Split the time string into hours and minutes and convert them into numbers
8 const [hours, minutes] = time.split(':').map(Number);
9 // Calculate the total minutes
10 return hours * 60 + minutes;
11}
12
13/**
14 * Calculates the number of full 15-minute rounds that can be played
15 * between a start time and a finish time.
16 * @param {string} startTime - Start time in the format of "HH:MM".
17 * @param {string} finishTime - Finish time in the format of "HH:MM".
18 * @returns {number} The number of full 15-minute rounds that can be played.
19 */
20function numberOfRounds(startTime: string, finishTime: string): number {
21 // Convert start and finish times to minutes
22 let startMinutes = toMinutes(startTime),
23 finishMinutes = toMinutes(finishTime);
24
25 // If the start time is after finish time, add 24 hours to finish time
26 if (startMinutes > finishMinutes) {
27 finishMinutes += 24 * 60; // Add one full day in minutes
28 }
29
30 // Calculate the number of full 15-minute rounds
31 const rounds = Math.floor(finishMinutes / 15) - Math.ceil(startMinutes / 15);
32
33 // Return positive number of full rounds or 0 if the result is negative
34 return rounds > 0 ? rounds : 0;
35}
36
Time and Space Complexity
Time Complexity
The time complexity of the numberOfRounds
function is O(1)
. This is because the function consists of a few arithmetic operations and conditional checks, which are all constant time operations. The function calculates the minutes for the start and finish times, then computes the rounds by dividing by 15. The constants do not scale with the size of the input, as the input is always a time in HH:MM
format.
Space Complexity
The space complexity of the numberOfRounds
function is also O(1)
. This function uses only a fixed number of integer variables to store the start and finish times, and for the intermediate calculations. It does not allocate any additional space that grows with the input size, resulting in constant space complexity.
Learn more about how to find time and space complexity quickly using problem constraints.
How does quick sort divide the problem into subproblems?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!