1344. Angle Between Hands of a Clock


Problem Description

In this problem, we are asked to find the smaller angle between the hour and minute hands of a clock based on the provided hour and minutes values. A clock is a circle, and a full circle is 360 degrees. As time progresses, both the hour and minute hands move around the clock at different speeds. The hour hand makes a complete rotation every 12 hours, while the minute hand does so every hour (60 minutes). The goal is to calculate the angle in degrees between the two hands, which could be thought of as two vectors originating from the center of the clock and pointing towards the current positions of the hands. Importantly, we want to find the smallest of the two possible angles created by these hands. The precision of the answer should be within 10^-5 degrees for it to be considered correct.

Intuition

To determine the angle between the hour and minute hands, we first calculate the angle of each hand relative to 12 o'clock, or 0 degrees. For the hour hand (h), it moves 30 degrees each hour (1/12 of a full circle) and an additional 0.5 degrees each minute (since it progresses 1/12 of an hour per 60 minutes). For the minute hand (m), it moves at a consistent pace of 6 degrees per minute (1/60 of a full circle).

Once we have the angles for each hand, we get the difference between them using abs(h - m). This gives us one of the angles created by the hour and minute hands—the larger one if it's over 180 degrees. To find the smaller angle, we simply subtract the larger angle from 360 degrees if necessary, since the sum of both angles is always 360 degrees (the full circle).

The use of min(diff, 360 - diff) gives us the smaller angle, as required by the problem statement. This is because the angle between the two hands must always be less than or equal to 180 degrees. If diff is greater than 180, 360 - diff gives us the smaller angle. If diff is less than or equal to 180, then it is already the smaller angle.

Learn more about Math patterns.

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

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Solution Approach

The approach used in the provided solution is straightforward and does not involve complex data structures or patterns. It focuses on mathematics and geometry concepts applied to the context of a clock.

Here is the breakdown of the implementation steps:

  1. Calculate the angle of the hour hand from 12 o'clock. This is done using the formula 30 * hour + 0.5 * minutes. Since there are 12 hours on a clock, the hour hand moves 360 degrees / 12 = 30 degrees every hour. Additionally, for every minute that passes, the hour hand will move an additional 0.5 degrees (30 degrees / 60 minutes), because it is gradually moving towards the next hour mark.

  2. Calculate the angle of the minute hand from 12 o'clock using the formula 6 * minutes. The minute hand moves 360 degrees / 60 = 6 degrees every minute.

  3. Find the absolute difference between these two angles with abs(h - m). This difference is one of the two angles formed by the hour and minute hands.

  4. The last step is to determine the smaller of the two possible angles. If the difference calculated is greater than half a rotation (180 degrees), the smaller angle would be the supplement of that angle, which is 360 degrees - diff. If it is less than 180 degrees, it is already the smaller angle. The min(diff, 360 - diff) function returns the smaller angle.

No further algorithms or complex data structures are used in this solution; the primary focus is on understanding the movement of the clock hands and applying basic arithmetic to find the desired angle.

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

Which data structure is used in a depth first search?

Example Walkthrough

Let's walk through a small example. Assume that we have hour = 3 and minutes = 30. We want to find the smaller angle between the hour and minute hands of a clock at 3:30.

  1. Calculate the angle of the hour hand from 12 o'clock:

    • Using the formula 30 * hour + 0.5 * minutes:
    • 30 * 3 + 0.5 * 30 = 90 + 15 = 105 degrees.
    • So, the angle for the hour hand from the 12 o'clock position is 105 degrees.
  2. Calculate the angle of the minute hand from 12 o'clock:

    • Using the formula 6 * minutes:
    • 6 * 30 = 180 degrees.
    • So, the angle for the minute hand from the 12 o'clock position is 180 degrees.
  3. Find the absolute difference between these two angles:

    • abs(h - m) = abs(105 - 180) = abs(-75) = 75 degrees.
    • The difference between the two angles is 75 degrees.
  4. Determine the smaller angle:

    • Since the difference is less than 180 degrees, the smaller angle is the same as the difference.
    • We use min(diff, 360 - diff) to confirm this:
    • min(75, 360 - 75) = min(75, 285) = 75 degrees.

The smaller angle between the hour and minute hands when the time is 3:30 is 75 degrees.

Not Sure What to Study? Take the 2-min Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Python Solution

1class Solution:
2    def angleClock(self, hour: int, minutes: int) -> float:
3        # Calculate the angle of the hour hand relative to 12:00.
4        # The hour hand moves 30 degrees every hour, plus an additional 0.5 degrees every minute.
5        hour_angle = 30 * hour + 0.5 * minutes
6
7        # Calculate the angle of the minute hand relative to 12:00.
8        # The minute hand moves 6 degrees every minute.
9        minute_angle = 6 * minutes
10
11        # Calculate the difference between the two angles.
12        angle_diff = abs(hour_angle - minute_angle)
13
14        # The angle between the two hands may be the smaller of the two possibilities:
15        # either angle_diff directly, or the complementary angle, which is 360 - angle_diff.
16        return min(angle_diff, 360 - angle_diff)
17

Java Solution

1class Solution {
2  
3    /**
4     * Calculates the smaller angle between the hour and minute hands of a clock.
5     * 
6     * @param hour The current hour shown by the clock.
7     * @param minutes The current minutes shown by the clock.
8     * @return The smaller angle between the hour and minute hands.
9     */
10    public double angleClock(int hour, int minutes) {
11        // Calculate the angle of the hour hand from 12 o'clock.
12        // The hour hand moves 0.5 degrees per minute (30 degrees per hour and 1/60 of that per minute).
13        double hourHandAngle = 30 * hour + 0.5 * minutes;
14      
15        // Calculate the angle of the minute hand from 12 o'clock.
16        // The minute hand moves 6 degrees per minute.
17        double minuteHandAngle = 6 * minutes;
18      
19        // Find the absolute difference between the two angles.
20        double angleDifference = Math.abs(hourHandAngle - minuteHandAngle);
21      
22        // Calculate the smaller angle between the two clock hands.
23        // It should be less than or equal to 180 degrees.
24        return Math.min(angleDifference, 360 - angleDifference);
25    }
26}
27

C++ Solution

1class Solution {
2public:
3    double angleClock(int hour, int minutes) {
4        // Calculate the angle of the hour hand
5        // The hour hand moves 30 degrees per hour plus another 0.5 degrees per minute
6        double hourAngle = 30 * hour + 0.5 * minutes;
7      
8        // Calculate the angle of the minute hand
9        // The minute hand moves 6 degrees per minute
10        double minuteAngle = 6 * minutes;
11      
12        // Calculate the absolute difference between the two angles
13        double angleDifference = abs(hourAngle - minuteAngle);
14      
15        // The angle should be the smaller one between angleDifference and 360 - angleDifference
16        // because the hands could be on either sides of each other
17        return min(angleDifference, 360 - angleDifference);
18    }
19};
20

Typescript Solution

1// Calculate the angle between the hour hand and the minute hand on a clock
2// @param {number} hour - The hour on the clock
3// @param {number} minutes - The minutes on the clock
4// @returns {number} - The smallest angle between the hour and minute hands
5function angleClock(hour: number, minutes: number): number {
6    // Calculate the position of the hour hand
7    // Each hour represents 30 degrees (360 degrees / 12 hours)
8    // Each minute adds 0.5 degrees to the hour hand (30 degrees / 60 minutes)
9    const hourHandPosition: number = 30 * hour + 0.5 * minutes;
10
11    // Calculate the position of the minute hand
12    // Each minute represents 6 degrees (360 degrees / 60 minutes)
13    const minuteHandPosition: number = 6 * minutes;
14
15    // Calculate the absolute difference between the two hands
16    const difference: number = Math.abs(hourHandPosition - minuteHandPosition);
17
18    // The angle between the hands could be the difference or 360 - difference
19    // We need the smallest angle
20    return Math.min(difference, 360 - difference);
21}
22
Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Time and Space Complexity

The code consists of simple arithmetic operations and a minimum of two values. Here is the analysis of its complexities:

  • Time Complexity: The algorithm computes the angle by performing a constant number of arithmetic operations, irrespective of the input size. Thus, the time complexity is O(1).

  • Space Complexity: It uses a fixed amount of space for the variables h, m, and diff and does not allocate any additional space that scales with the input size. Therefore, the space complexity is also O(1).

Learn more about how to find time and space complexity quickly.


Recommended Readings


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 👨‍🏫