1904. The Number of Full Rounds You Have Played

MediumMathString
Leetcode Link

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 than loginTime, this suggests the user played from loginTime through midnight to the next day, until logoutTime.

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:

  1. Convert both loginTime and logoutTime 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.

  2. Account for the scenario when logoutTime is earlier than loginTime. This indicates that the user played through midnight. To manage this, 24 hours (1440 minutes) are added to logoutTime to properly calculate the number of rounds.

  3. 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 the logoutTime, we need to round it down to the closest round start time that has been completed.

  4. 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 after loginTime, hence, we use max(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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What is the running time of the following code?

1int sqrt(int n) {
2  for (int guess = 1; guess * guess <= n; guess++) {
3    if (guess * guess == n) {
4      return guess;
5    }
6  }
7  return -1;
8}

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:

  1. A helper function named get is defined, which takes a string s 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.

  2. The startTime and finishTime are then converted to minutes using the helper function get.

  3. We then check if the startTime is greater than the finishTime. If it is, it means the player has played overnight, and therefore we add 24 hours (1440 minutes) to the finishTime.

  4. 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 or 00: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.

  5. 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.

  6. 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 the startTime. We use max(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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?

Example 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:

  1. Convert loginTime and logoutTime to minutes:

    • get("22:47") would result in 22 * 60 + 47 = 1367 minutes.
    • get("01:12") would result in 1 * 60 + 12 = 72 minutes.

  2. Since logoutTime is on the next day (01:12 is after midnight), we add 1440 minutes (a full day) to logoutTime to get the correct duration:

    • Updated logoutTime in minutes: 72 + 1440 = 1512 minutes.

  3. 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.)

  4. 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.

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
Not Sure What to Study? Take the 2-min Quiz：

Which data structure is used in a depth first search?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Math Basics

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫