The Number of Full Rounds You Have Played

Medium

Asked by:

8 views

Topics:

ArraysStrings

You are participating in an online chess tournament. There is a chess round that starts every 15 minutes. The first round of the day starts at 00:00, and after every 15 minutes, a new round starts.

For example, the second round starts at 00:15, the fourth round starts at 00:45, and the seventh round starts at 01:30.

You are given two strings loginTime and logoutTime where:

loginTime is the time you will login to the game, and
logoutTime is the time you will logout from the game.

If logoutTime is earlier than loginTime, this means you have played from loginTime to midnight and from midnight to logoutTime.

Return the number of full chess rounds you have played in the tournament.

Note: All the given times follow the 24-hour clock. That means the first round of the day starts at 00:00 and the last round of the day starts at 23:45.

Example 1:

Input: loginTime = "09:31", logoutTime = "10:14"
Output: 1
Explanation: You played one full round from 09:45 to 10:00.
You did not play the full round from 09:30 to 09:45 because you logged in at 09:31 after it began.
You did not play the full round from 10:00 to 10:15 because you logged out at 10:14 before it ended.

Example 2:

Input: loginTime = "21:30", logoutTime = "03:00"
Output: 22
Explanation: You played 10 full rounds from 21:30 to 00:00 and 12 full rounds from 00:00 to 03:00.
10 + 12 = 22.

Constraints:

loginTime and logoutTime are in the format hh:mm.
00 <= hh <= 23
00 <= mm <= 59
loginTime and logoutTime are not equal.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Are the start and finish times guaranteed to be valid times in the HH:MM format, and will startTime always be before or equal to finishTime?
If the finishTime is earlier than the startTime (e.g., startTime is '23:45' and finishTime is '00:15'), should I assume the finishTime is on the next day?
If the start and finish times fall within the same 15-minute interval (e.g., startTime is '10:00' and finishTime is '10:10'), should I return 0?
Is it possible for the startTime and finishTime to be exactly the same, and if so, what should the return value be?
Can you provide a few more examples to illustrate edge cases or boundary conditions, especially regarding times that fall exactly on the 15-minute marks (e.g., '10:00', '10:15', '10:30', '10:45')?

Brute Force Solution

Approach

We want to find out how many complete time periods fit between a start time and an end time. The brute force method involves checking every possible complete time period one by one to see if it fits.

Here's how the algorithm would work step-by-step:

Figure out the starting time, and the ending time of the overall period we are looking at.
Determine the length of a single complete time period, for example 15 minutes.
Start at the beginning time and add the length of one complete time period.
Check if adding that full time period puts us before the end time. If it does, that means one full time period fits.
If it fits, add another full time period to the start time.
Again, check if the new time is before the end time, meaning another full time period fits.
Keep adding full time periods one at a time, and checking if the resulting time is still before the end time. Each time it is, increase our count of full time periods that fit.
Stop when adding another full time period would make the resulting time equal to, or after, the end time. The count we have at this point represents how many full time periods fit.

Code Implementation

def the_number_of_full_rounds_you_have_played(start_time, end_time, length_of_round):
    number_of_rounds_played = 0
    current_time = start_time

    # Keep going as long as we can fit another round
    while True:
        next_time = current_time + length_of_round

        # If adding another round puts us at or after the end, then exit
        if next_time > end_time:
            break

        # Count the fact that we fit in another round
        number_of_rounds_played += 1

        # Set the start of the next round
        current_time = next_time

    return number_of_rounds_played

Big(O) Analysis

Time Complexity

O(n) – The algorithm iteratively adds a fixed time period to the start time and checks if the result is still before the end time. The number of iterations, n, is dependent on how many full time periods fit between the start and end times. In the worst case, if the time period is very small, the number of iterations (and therefore comparisons) could be proportional to the difference between the start and end times divided by the time period. This makes the time complexity linear with respect to the number of full time periods that can fit between the given start and end times.

Space Complexity

O(1) – The algorithm, as described, calculates the number of full rounds by iteratively adding the round length to the start time and comparing it to the end time. It primarily uses variables to store the start time, end time, round length, and a counter for the number of full rounds. These variables take up a constant amount of space regardless of the difference between the start and end times, so the auxiliary space doesn't depend on any input parameter N (where N could represent the time difference). Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the number of full game rounds completed within a given time interval, we focus on aligning start and end times to the nearest round boundaries. We compute how many rounds can start after the starting time, and how many rounds completed before the ending time, and subtract appropriately.

Here's how the algorithm would work step-by-step:

First, figure out when the first complete round can begin, based on the given starting time.
Then, find out when the last complete round finished before the given ending time.
Calculate the difference between these two aligned times.
Divide the difference by the round length to determine the total number of complete rounds that occurred within that time period.

Code Implementation

def numberOfRounds(startTime, finishTime):
    startHour, startMinute = map(int, startTime.split(':'))
    finishHour, finishMinute = map(int, finishTime.split(':'))

    startTotalMinutes = startHour * 60 + startMinute
    finishTotalMinutes = finishHour * 60 + finishMinute

    # Handle the case where the game wraps around midnight
    if finishTotalMinutes < startTotalMinutes:
        finishTotalMinutes += 24 * 60

    # Find the start of the first complete round after the start time.
    alignedStartTime = (startTotalMinutes + 14) // 15 * 15

    # Find the end of the last complete round before the finish time.
    alignedFinishTime = finishTotalMinutes // 15 * 15

    # Ensure aligned times are valid
    if alignedStartTime > alignedFinishTime:
        return 0

    # Calculate and return the number of full rounds
    return (alignedFinishTime - alignedStartTime) // 15

Big(O) Analysis

Time Complexity

O(1) – The solution involves a fixed number of arithmetic operations to calculate the aligned start and end times and then compute the difference and divide. The number of operations does not depend on the size of any input array or other variable. Therefore, the time complexity is constant, or O(1).

Space Complexity

O(1) – The algorithm calculates the start time of the first complete round and the end time of the last complete round. These calculations utilize a few constant space variables to store intermediate time values. No auxiliary data structures that scale with the input size are created or used, hence the space complexity is constant. Therefore, the space used by this algorithm does not depend on the input size N, and it remains constant.

Edge Cases

Case	How to Handle
startTime and finishTime are equal, but not at the start of a 15-minute interval (e.g., '10:07')	The number of rounds is zero if the start and end times are the same and not on a 15-minute boundary.
startTime and finishTime are equal and at the start of a 15-minute interval (e.g., '10:00')	The number of rounds is still zero if the start and end times are the same and on a 15-minute boundary.
startTime is later than finishTime (e.g., '23:50' and '00:10')	Handle wraparound by adding a day (24 hours or 1440 minutes) to finishTime when startTime is later.
startTime or finishTime is invalid (e.g., '25:00', '10:60')	Validate the input strings and throw an exception or return an error code if the format is invalid.
startTime and finishTime are very close, less than 15 minutes apart (e.g., '10:01' and '10:14')	The number of rounds is zero if the difference between the rounded start and end times is less than 15 minutes.
startTime is at the very end of a 15-minute interval and finishTime is at the start of an interval (e.g. 10:14 and 10:15)	No full 15-minute intervals are possible, so the result should be zero.
startTime is '00:00' and finishTime is '23:59'	Calculate full rounds within the 24 hour period, which is (24 * 60) / 15 - 1 because the last interval is not complete.
The input strings are null or empty.	Check for null or empty inputs and return 0 or throw an IllegalArgumentException accordingly.

startTime and finishTime are equal, but not at the start of a 15-minute interval (e.g., '10:07')

How to Handle:

The number of rounds is zero if the start and end times are the same and not on a 15-minute boundary.

startTime and finishTime are equal and at the start of a 15-minute interval (e.g., '10:00')

How to Handle:

The number of rounds is still zero if the start and end times are the same and on a 15-minute boundary.

startTime is later than finishTime (e.g., '23:50' and '00:10')

How to Handle:

Handle wraparound by adding a day (24 hours or 1440 minutes) to finishTime when startTime is later.

startTime or finishTime is invalid (e.g., '25:00', '10:60')

How to Handle:

Validate the input strings and throw an exception or return an error code if the format is invalid.

startTime and finishTime are very close, less than 15 minutes apart (e.g., '10:01' and '10:14')

How to Handle:

The number of rounds is zero if the difference between the rounded start and end times is less than 15 minutes.

startTime is at the very end of a 15-minute interval and finishTime is at the start of an interval (e.g. 10:14 and 10:15)

How to Handle:

No full 15-minute intervals are possible, so the result should be zero.

startTime is '00:00' and finishTime is '23:59'

How to Handle:

Calculate full rounds within the 24 hour period, which is (24 * 60) / 15 - 1 because the last interval is not complete.

The input strings are null or empty.

How to Handle:

Check for null or empty inputs and return 0 or throw an IllegalArgumentException accordingly.