Условие

Бинарные часы отображают время с помощью светодиодов: 4 светодиода представляют часы (0–11), 6 светодиодов представляют минуты (0–59). Каждый светодиод может быть включен (1) или выключен (0). Дано неотрицательное целое число turnedOn, представляющее количество включенных светодиодов. Необходимо вернуть все возможные комбинации времени, которые могут быть отображены на часах.

Примеры

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

Input: turnedOn = 9 Output: []

Решение

fun readBinaryWatch(turnedOn: Int): List<String> {
    val result = mutableListOf<String>()

    // Перебираем все возможные часы (0-11) и минуты (0-59)
    for (h in 0 until 12) {
        for (m in 0 until 60) {
            // Проверяем количество единиц в двоичном представлении часов и минут
            if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                // Форматируем строку в виде "h:mm" с двухзначными минутами
                result.add("$h:${String.format("%02d", m)}")
            }
        }
    }

    return result
}

Временная сложность

O(1), так как общее количество комбинаций фиксировано (12 * 60 = 720).

Пространственная сложность

O(1), если не учитывать пространство для хранения результата.