401. Binary Watch

Time: O(1)

Space: O(1)

Intuition

Enumerate all valid times (hours 0 - 11, minutes 0 - 59) and count the number of 1-bits in the combined binary representation (hours take 4 bits, minutes take 6 bits). If bit count == num, add the time to results.

Algorithm

1For h from 0 to 11: for m from 0 to 59: if BitCount(h)+BitCount(m)==num: add "{h}:{m:D2}" to results.

Example Walkthrough

Input: num = 1

1.h=0,m=1: bits=0+1=1 -> "0:01". h=0,m=2: 1 bit -> "0:02". ... h=1,m=0: 1+0=1 -> "1:00". Etc.

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

Common Pitfalls

•Format minutes with leading zero - "0:1" is wrong, must be "0:01".

401.cs

// Approach: DFS choosing turnedOn LEDs from the 10 positions (4 hours + 6 mins);
// record the time when all LEDs are assigned and it represents a valid time.
// Time: O(1) Space: O(1)

public class Solution
{
    public IList<string> ReadBinaryWatch(int turnedOn)
    {
        List<string> ans = new List<string>();
        Dfs(turnedOn, 0, 0, 0, ans);
        return ans;
    }

    private int[] hours = new int[] { 1, 2, 4, 8 };
    private int[] minutes = new int[] { 1, 2, 4, 8, 16, 32 };

    private void Dfs(int turnedOn, int s, int h, int m, List<string> ans)
    {
        if (turnedOn == 0)
        {
            string time = h + ":" + (m < 10 ? "0" : "") + m;
            ans.Add(time);
            return;
        }

        for (int i = s; i < hours.Length + minutes.Length; ++i)
        {
            if (i < 4 && h + hours[i] < 12)
                Dfs(turnedOn - 1, i + 1, h + hours[i], m, ans);
            else if (i >= 4 && m + minutes[i - 4] < 60)
                Dfs(turnedOn - 1, i + 1, h, m + minutes[i - 4], ans);
        }
    }
}

public class Solution1
{
    public IList<string> ReadBinaryWatch(int turnedOn)
    {
        var ans = new List<string>();

        for (int h = 0; h < 12; ++h)
            for (int m = 0; m < 60; ++m)
                if (CountBits(h) + CountBits(m) == turnedOn)
                    ans.Add(h + (m < 10 ? ":0" : ":") + m);

        return ans;
    }

    private int CountBits(int n)
    {
        int count = 0;
        while (n > 0)
        {
            count += n & 1;
            n >>= 1;
        }
        return count;
    }
}

Was this solution helpful?