Binary Watch

🏠 ⬅️ ➡️

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

  • For example, the below binary watch reads "4:51 ".

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

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

Example 1:

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

Example 2:

Input: turnedOn = 9 Output: []

Constraints:

  • 0 <= turnedOn <= 10
Note: This problem is from LeetCode.
✅ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer :: i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
    integer :: turnedOn
    character(len=5) :: time
    character(len=10) :: times(10)

    ! Examples from the problem statement
    turnedOn = 1
    call solve(turnedOn, times)
    write (*, '(A)') times

    turnedOn = 9
    call solve(turnedOn, times)
    write (*, '(A)') times

contains

subroutine solve(turnedOn, times)
    implicit none
    integer, intent(in) :: turnedOn
    character(len=5), intent(out) :: times(:)

    integer :: h, m

    do i = 0, 11
        do j = 0, 59
            if (i == 0 .and. j < 10) then
                cycle
            end if
            if (i > 0 .and. j < 10) then
                cycle
            end if
            if (mod(i * 10 + j, turnedOn) /= 0) then
                cycle
            end if
            h = i
            m = j
            if (h < 10) then
                write (time, '(I1, ":", I2)') h, m
            else
                write (time, '(I2, ":", I2)') h, m
            end if
            times(i * 6 + j + 1) = time
        end do
    end do
end subroutine solve

end program main
❌ Compiled
❌ Executed
❌ Correct 
module binary_watch

implicit none

contains

function get_times(turned_on) result(times)

integer, intent(in) :: turned_on
type(time_t) :: times(0:59)

integer :: hour, minute

do hour = 0, 11
do minute = 0, 59

if (get_bit(hour, turned_on) .and. get_bit(minute, turned_on)) then

times(minute)%hour = hour
times(minute)%minute = minute

end if

end do
end do

end function get_times

function get_bit(n, i) result(bit)

integer, intent(in) :: n, i
logical :: bit

bit = mod(n, 2**i) >= 2**(i-1)

end function get_bit

end module binary_watch

program main

use binary_watch

implicit none

integer :: i, turned_on
type(time_t) :: times(0:59)

turned_on = 1
times = get_times(turned_on)

do i = 1, size(times)

write (*,*) times(i)%hour, ":", times(i)%minute

end do

turned_on = 9
times = get_times(turned_on)

if (size(times) == 0) then

write (*,*) "No times found"

else

do i = 1, size(times)

write (*,*) times(i)%hour, ":", times(i)%minute

end do

end if

end program main

type time_t

integer :: hour, minute

end type time_t
🌐 Data from online sources 
def readBinaryWatch(turnedOn: int):
    def count_bits(n):
        return bin(n).count('1')

    times = []
    for h in range(12):
        for m in range(60):
            if count_bits(h) + count_bits(m) == turnedOn:
                times.append(f"{h}:{m:02d}")
    return times

The algorithm consists of enumerating all possible hour values (0-11) and minute values (0-59), and checking the number of bits set in both. We have a helper function count_bits (or named similarly) in each language to count the number of bits set in the binary representation of a given value. The function either uses the built-in bit counting function (__builtin_popcount in C++, Integer.bitCount in Java), or in Python and JavaScript, we convert the numbers to binary strings and count the number of '1's.

For each pair (h, m), if the total number of turned-on LEDs is equal to the given integer turnedOn, we add the corresponding formatted string to the result list. In the end, we return the list of all possible times.

🌐 Data from online sources 
#include <vector>
#include <string>
using namespace std;

vector<string> readBinaryWatch(int turnedOn) {
    vector<string> times;
    for (int h = 0; h < 12; h++) {
        for (int m = 0; m < 60; m++) {
            if (__builtin_popcount(h) + __builtin_popcount(m) == turnedOn) {
                times.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));
            }
        }
    }
    return times;
}

The algorithm consists of enumerating all possible hour values (0-11) and minute values (0-59), and checking the number of bits set in both. We have a helper function count_bits (or named similarly) in each language to count the number of bits set in the binary representation of a given value. The function either uses the built-in bit counting function (__builtin_popcount in C++, Integer.bitCount in Java), or in Python and JavaScript, we convert the numbers to binary strings and count the number of '1's.

For each pair (h, m), if the total number of turned-on LEDs is equal to the given integer turnedOn, we add the corresponding formatted string to the result list. In the end, we return the list of all possible times.