LeetCode Entry

401. Binary Watch

17.02.2026 easy 2026 kotlin rust

All times with count bits set

401. Binary Watch easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1272

Problem TLDR

All times with count bits set #easy #brainteaser

Intuition

Not an easy problem.

    // i don't understand the description
    // is AM/PM a separate bit?
    // H: 8 4 2 1
    // M: 32 16 8 4 2 1
    // input is count of turned on bits?
    // t=1, should be 10 results - correct
    // now we need:
    // dfs to collect all possible bits permutations
    // (1 shl (t-1))
    // then a way to convert a bitmask to the time string
    // or maybe inversed problem is simpler:
    // iterate hours and minutes, convert to bits, check count
    //
    // how to convert numbe to bits?
    // 3: 11, ITS just a binary representation

The brainteaser brute-force: check every hour-minute pair. The honest worker solution: backtrack every set bit of possible 10 bit positions. The hard solution: compute next smallest bitmask with set bits.

Approach

• hours to bits conversion: just a binary representation
• bits to hours conversion: just an int value of a bitmask
• only 720 possible values (60*12)
• we can call countOneBits once on H*64+M
• use format or padStart
• next smallest bitmask: mode left the first 1-bit of the ‘11..’s tail, put leftower ‘11..’s-1 tail to the end (100110 becomes 101011)

Complexity

• Time complexity: \(O(h*m)\)

• Space complexity: \(O(h*m)\)

Code

// 25ms
    fun readBinaryWatch(t: Int) = (0..719)
    .filter { (it/60 * 64 + it%60).countOneBits() == t }
    .map { "%d:%02d".format(it/60,it%60) }

// 0ms
    pub fn read_binary_watch(t: i32) -> Vec<String> {
        successors(Some((1<<t)-1), |&s:&i32| {
            let tz = s.trailing_zeros(); let to = (s >> tz).trailing_ones();
            (tz + to < 10).then(|| s + (1 << tz) + (1 << (to - 1)) - 1)
        })
        .filter_map(|s| {
            let (h,m) = (s>>6, s&63);
            (h < 12 && m < 60).then(|| format!("{}:{:02}", h, m))
        }).collect()
    }