401. Binary Watch

leetcode easy

#bit-manipulation#csharp#easy#graph#leetcode#string

Task

Бинарные часы имеют 4 светодиода сверху для представления часов (0-11) и 6 светодиодов снизу для представления минут (0-59). Каждый светодиод представляет ноль или единицу, при этом младший разряд находится справа.

Пример:

Input: turnedOn = 1

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

C# solution

matched/original

public class Solution {
    public IList<string> ReadBinaryWatch(int turnedOn) {
        var results = new List<string>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    results.Add($"{h}:{m:D2}");
                }
            }
        }
        return results;
    }
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> ReadBinaryWatch(int turnedOn) {
        var results = new List<string>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (CountBits(h) + CountBits(m) == turnedOn) {
                    results.push_back($"{h}:{m:D2}");
                }
            }
        }
        return results;
    }
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Java solution

matched/original

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> results = new ArrayList<>();
        for (int h = 0; h < 12; h++) {
            for (int m = 0; m < 60; m++) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    results.add(String.format("%d:%02d", h, m));
                }
            }
        }
        return results;
    }
}

JavaScript solution

matched/original

class Solution {
    readBinaryWatch(turnedOn) {
        const results = [];
        for (let h = 0; h < 12; h++) {
            for (let m = 0; m < 60; m++) {
                if (h.toString(2).split('1').length - 1 + m.toString(2).split('1').length - 1 === turnedOn) {
                    results.push(`${h}:${m.toString().padStart(2, '0')}`);
                }
            }
        }
        return results;
    }
}

Python solution

matched/original

class Solution:
    def readBinaryWatch(self, turnedOn: int) -> List[str]:
        results = []
        for h in range(12):
            for m in range(60):
                if bin(h).count('1') + bin(m).count('1') == turnedOn:
                    results.append(f"{h}:{m:02d}")
        return results

Explanation

Algorithm

Генерация всех возможных комбинаций:

Переберите все возможные значения для часов и минут.

Используйте битовые операции для подсчета количества единиц в бинарном представлении числа.

Проверка количества горящих светодиодов:

Для каждой комбинации проверьте, соответствует ли сумма единиц в бинарном представлении часов и минут заданному количеству горящих светодиодов.

Форматирование результата:

Если комбинация часов и минут соответствует условию, отформатируйте их в виде строки "часы:минуты" и добавьте в список результатов.

😎