LeetCode 401. Binary Watch

Question

• https://leetcode.com/problems/binary-watch/

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.

Given an integer turnedOn which represents the number of LEDs that are currently on, 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".

• binary watchは、上部の4つのLEDが時間（0〜11）を表し、下部の6つのLEDが分（0〜59）を表す。
• 各LEDは0または1を表し、最下位ビットは一番右側。
• 点灯しているLEDの数を表す整数 turnedOn が与えられたら、その時計が表すことのできるすべての時間を返す。
• 答えを返す順序は自由
• 時間には先頭にゼロがあってはいけない。例えば、"01:00"は無効とされ、"1:00"となる。
• 分は2桁の数字で、1桁の場合、先頭をゼロ埋めする。例えば、"10:2"は無効とされ、"10:02 "となる

Code

class Solution {
    fun readBinaryWatch(turnedOn: Int): List<String> {
        var answer = mutableListOf<String>()

        fun bitCount(num: Int): Int {
            var tmp = num
            var cnt = 0
            while (tmp > 0) {
                cnt += tmp % 2
                tmp /= 2
            }
            return cnt
        }

        for (h in 0..11) {
            for (m in 0..59) {
                if (bitCount(h) + bitCount(m) == turnedOn) {
                    answer.add("$h:${if (m < 10) "0$m" else "$m"}")
                }
            }
        }
        return answer
    }
}

入力されたturnedOnを満たす時間について、
0:00~12:59までを1分ずつ見ていっても、12*60の探索でO(1)
時間と分に分けてそれぞれ2進数にしたときに1となる桁をカウントした和を求めればよい。
fun bitCount(num: Int)は、商が0になるまで、変換したい10進数を2で割り続けて余りを下から読む一般的な変換方法にカウンタをもたせたものである。(2の剰余は0か1としかならないので、脳死で足し続けてよい。)

コロン右側の分側は、1桁のときに0埋めをする必要があるので、validとなるように忘れないようにしないといけない。

Profile

• Runtime: 197 ms
• Memory Usage: 34.8 MB

Submission

• https://leetcode.com/submissions/detail/593329702/