401. Binary Watch

Problem

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.

For example, the above binary watch reads "3:25".

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

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

Note:

The order of output does not matter.
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".

Problem Summary

A binary watch has 4 LEDs on the top representing hours (0-11), and 6 LEDs on the bottom representing minutes (0-59). Each LED represents a 0 or 1, with the least significant bit on the right.

Given a non-negative integer n representing the number of LEDs that are currently on, return all possible times the binary watch could represent.

Solution Approach

Given the number n, output all possible times on the binary watch.
The tricky part of the problem is that minutes greater than 60 should not be printed, and hours greater than 12 should not be printed either, because they are invalid. If the given num is greater than 8, it is also an invalid value, and the final result should be an empty string array.
The data size for this problem is not large, so a lookup table can be used directly. For the specific table-generation functions, see the two functions findReadBinaryWatchMinute() and findReadBinaryWatchHour().

Code


package leetcode

import (
	"fmt"
	"strconv"
)

// Solution 1
func readBinaryWatch(num int) []string {
	memo := make([]int, 60)
	// count the number of 1 in a binary number
	count := func(n int) int {
		if memo[n] != 0 {
			return memo[n]
		}
		originN, res := n, 0
		for n != 0 {
			n = n & (n - 1)
			res++
		}
		memo[originN] = res
		return res
	}
	// fmtMinute format minute 0:1 -> 0:01
	fmtMinute := func(m int) string {
		if m < 10 {
			return "0" + strconv.Itoa(m)
		}
		return strconv.Itoa(m)
	}

	var res []string
	// traverse 0:00 -> 12:00
	for i := 0; i < 12; i++ {
		for j := 0; j < 60; j++ {
			if count(i)+count(j) == num {
				res = append(res, strconv.Itoa(i)+":"+fmtMinute(j))
			}
		}
	}
	return res
}

// Solution 2 Lookup table
var (
	hour    = []string{"1", "2", "4", "8"}
	minute  = []string{"01", "02", "04", "08", "16", "32"}
	hourMap = map[int][]string{
		0: {"0"},
		1: {"1", "2", "4", "8"},
		2: {"3", "5", "9", "6", "10"},
		3: {"7", "11"},
	}
	minuteMap = map[int][]string{
		0: {"00"},
		1: {"01", "02", "04", "08", "16", "32"},
		2: {"03", "05", "09", "17", "33", "06", "10", "18", "34", "12", "20", "36", "24", "40", "48"},
		3: {"07", "11", "19", "35", "13", "21", "37", "25", "41", "49", "14", "22", "38", "26", "42", "50", "28", "44", "52", "56"},
		4: {"15", "23", "39", "27", "43", "51", "29", "45", "53", "57", "30", "46", "54", "58"},
		5: {"31", "47", "55", "59"},
	}
)

func readBinaryWatch1(num int) []string {
	var res []string
	if num > 8 {
		return res
	}
	for i := 0; i <= num; i++ {
		for j := 0; j < len(hourMap[i]); j++ {
			for k := 0; k < len(minuteMap[num-i]); k++ {
				res = append(res, hourMap[i][j]+":"+minuteMap[num-i][k])
			}
		}
	}
	return res
}

/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
/// ---------------------------------------
// The following are functions used for generating the lookup table
// Call findReadBinaryWatchMinute(num, 0, c, &res) to generate the lookup table
func findReadBinaryWatchMinute(target, index int, c []int, res *[]string) {
	if target == 0 {
		str, tmp := "", 0
		for i := 0; i < len(c); i++ {
			t, _ := strconv.Atoi(minute[c[i]])
			tmp += t
		}
		if tmp < 10 {
			str = "0" + strconv.Itoa(tmp)
		} else {
			str = strconv.Itoa(tmp)
		}
		// fmt.Printf("Found a solution c = %v str = %v\n", c, str)
		fmt.Printf("\"%v\", ", str)
		return
	}
	for i := index; i < 6; i++ {
		c = append(c, i)
		findReadBinaryWatchMinute(target-1, i+1, c, res)
		c = c[:len(c)-1]
	}
}

// Call findReadBinaryWatchHour(num, 0, c, &res) to generate the lookup table
func findReadBinaryWatchHour(target, index int, c []int, res *[]string) {
	if target == 0 {
		str, tmp := "", 0
		for i := 0; i < len(c); i++ {
			t, _ := strconv.Atoi(hour[c[i]])
			tmp += t
		}
		str = strconv.Itoa(tmp)
		//fmt.Printf("Found a solution c = %v str = %v\n", c, str)
		fmt.Printf("\"%v\", ", str)
		return
	}
	for i := index; i < 4; i++ {
		c = append(c, i)
		findReadBinaryWatchHour(target-1, i+1, c, res)
		c = c[:len(c)-1]
	}
}