Posts tagged as “clock”

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

By zxi on August 15, 2021

A new online video game has been released, and in this video game, there are 15-minute rounds scheduled every quarter-hour period. This means that at HH:00, HH:15, HH:30 and HH:45, a new round starts, where HH represents an integer number from 00 to 23. A 24-hour clock is used, so the earliest time in the day is 00:00 and the latest is 23:59.

Given two strings startTime and finishTime in the format "HH:MM" representing the exact time you started and finished playing the game, respectively, calculate the number of full rounds that you played during your game session.

For example, if startTime = "05:20" and finishTime = "05:59" this means you played only one full round from 05:30 to 05:45. You did not play the full round from 05:15 to 05:30 because you started after the round began, and you did not play the full round from 05:45 to 06:00 because you stopped before the round ended.

If finishTime is earlier than startTime, this means you have played overnight (from startTime to the midnight and from midnight to finishTime).

Return the number of full rounds that you have played if you had started playing at startTime and finished at finishTime.

Example 1:

Input: startTime = "12:01", finishTime = "12:44"
Output: 1
Explanation: You played one full round from 12:15 to 12:30.
You did not play the full round from 12:00 to 12:15 because you started playing at 12:01 after it began.
You did not play the full round from 12:30 to 12:45 because you stopped playing at 12:44 before it ended.

Example 2:

Input: startTime = "20:00", finishTime = "06:00"
Output: 40
Explanation: You played 16 full rounds from 20:00 to 00:00 and 24 full rounds from 00:00 to 06:00.
16 + 24 = 40.

Example 3:

Input: startTime = "00:00", finishTime = "23:59"
Output: 95
Explanation: You played 4 full rounds each hour except for the last hour where you played 3 full rounds.

Constraints:

startTime and finishTime are in the format HH:MM.
00 <= HH <= 23
00 <= MM <= 59
startTime and finishTime are not equal.

Solution: String / Simple math

ans = max(0, floor(end / 15) – ceil(start / 15))

Tips:

Write a reusable function to parse time to minutes.
a / b for floor, (a + b – 1) / b for ceil

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

C++

// Author: Huahua

class Solution {

public:

int numberOfRounds(string startTime, string finishTime) {

auto parseTime = [](string t) {

return ((t[0] - '0') * 10 + (t[1] - '0')) * 60 + (t[3] - '0') * 10 + t[4] - '0';

};

int m1 = parseTime(startTime);

int m2 = parseTime(finishTime);

if (m2 < m1) m2 += 24 * 60;

return max(0, m2 / 15 - (m1 + 14) / 15);

}

};

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

By zxi on January 23, 2021

You are given a string time in the form of hh:mm, where some of the digits in the string are hidden (represented by ?).

The valid times are those inclusively between 00:00 and 23:59.

Return the latest valid time you can get from time by replacing the hidden digits.

Example 1:

Input: time = "2?:?0"
Output: "23:50"
Explanation: The latest hour beginning with the digit '2' is 23 and the latest minute ending with the digit '0' is 50.

Example 2:

Input: time = "0?:3?"
Output: "09:39"

Example 3:

Input: time = "1?:22"
Output: "19:22"

Constraints:

time is in the format hh:mm.
It is guaranteed that you can produce a valid time from the given string.

Solution 1: Brute Force

Enumerate all possible clock in reverse order and find the first matching one.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

for (int m = 60 * 24 - 1; m >= 0; --m) {

int hh = m / 60;

int mm = m % 60;

if (time[0] != '?' && time[0] - '0' != hh / 10) continue;

if (time[1] != '?' && time[1] - '0' != hh % 10) continue;

if (time[3] != '?' && time[3] - '0' != mm / 10) continue;

if (time[4] != '?' && time[4] - '0' != mm % 10) continue;

time[0] = (hh / 10) + '0';

time[1] = (hh % 10) + '0';

time[3] = (mm / 10) + '0';

time[4] = (mm % 10) + '0';

break;

}

return time;

}

};

Solution 2: Rules

Using rules, fill from left to right.

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

C++

// Author: Huahua

class Solution {

public:

string maximumTime(string time) {

if (time[0] == '?') time[0] = time[1] >= '4' && time[1] <= '9' ? '1' : '2';

if (time[1] == '?') time[1] = time[0] == '2' ? '3' : '9';

if (time[3] == '?') time[3] = '5';

if (time[4] == '?') time[4] = '9';

return time;

}

};

花花酱 LeetCode 1344. Angle Between Hands of a Clock

By zxi on February 13, 2020

Given two numbers, hour and minutes. Return the smaller angle (in sexagesimal units) formed between the hour and the minute hand.

Example 1:

Input: hour = 12, minutes = 30
Output: 165

Example 2:

Input: hour = 3, minutes = 30
Output: 75

Example 3:

Input: hour = 3, minutes = 15
Output: 7.5

Example 4:

Input: hour = 4, minutes = 50
Output: 155

Example 5:

Input: hour = 12, minutes = 0
Output: 0

Constraints:

1 <= hour <= 12
0 <= minutes <= 59
Answers within 10^-5 of the actual value will be accepted as correct.

Solution: Math

Compute the angle of the hour hand (h + m / 60.0) * 360 / 12 as a_h
Compute the angle of the minute hand m / 60.0 * 360 as a_m
ans = min(abs(a_h – a_m), 360 – abs(a_h – a_m))

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

C++

// Author: Huahua

class Solution {

public:

double angleClock(int hour, int minutes) {

double a_m = minutes * 360 / 60;

double a_h = (hour + minutes / 60.0) * 360 / 12;

return min(abs(a_m - a_h), 360 - abs(a_m - a_h));

}

};

花花酱 LeetCode 539. Minimum Time Difference

By zxi on March 21, 2018

Problem

Given a list of 24-hour clock time points in “Hour:Minutes” format, find the minimum minutes difference between any two time points in the list.

Example 1:

Input: ["23:59","00:00"]
Output: 1

Note:

The number of time points in the given list is at least 2 and won’t exceed 20000.
The input time is legal and ranges from 00:00 to 23:59.

Solution

Time complexity: O(nlog1440)

Space complexity: O(n)

C++

// Author: huahua

// Running time: 16 ms

class Solution {

public:

int findMinDifference(vector<string>& timePoints) {

constexpr int kMins = 24 * 60;

set<int> seen;

for (const string& time : timePoints) {

int m = stoi(time.substr(0, 2)) * 60 + stoi(time.substr(3));

if (!seen.insert(m).second) return 0;

}

int ans = (*seen.begin() - *seen.rbegin() + kMins) % kMins;

const int* l = nullptr;

for (const int& t : seen) {

if (l) ans = min(ans, t - *l);

l = &t;

}

return ans;

}

};

花花酱 LeetCode 401. Binary Watch

By zxi on March 17, 2018

Problem:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution 1:

Time complexity: O(11*59*n)

C++

// Author: Huahua

// Running time: 2 ms (beats 100%)

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> ans;

for (int i = 0; i <= num; ++i)

for (int h : nums(i, 12))

for (int m : nums(num - i, 60))

ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;

}

private:

// Return numbers in [0,r) that has b 1s in their binary format.

vector<int> nums(int b, int r) {

vector<int> ans;

for (int n = 0; n < r; ++n)

if (__builtin_popcount(n) == b) ans.push_back(n);

return ans;

}

};

Posts tagged as “clock”

花花酱 LeetCode 1904. The Number of Full Rounds You Have Played

Solution: String / Simple math

C++

花花酱 LeetCode 1736. Latest Time by Replacing Hidden Digits

Solution 1: Brute Force

C++

Solution 2: Rules

C++

花花酱 LeetCode 1344. Angle Between Hands of a Clock

C++

花花酱 LeetCode 539. Minimum Time Difference

Problem

Solution

花花酱 LeetCode 401. Binary Watch

Problem:

<img src="https://upload.wikimedia.org/wikipedia/commons/8/8b/Binary_clock_samui_moon.jpg" height="300"/>

Solution 1: