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 = 1Return: ["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".
Solution (Java)
public class BinaryWatch {
/**
* the first 4th bits are hours (1,2,4,8)
* the next 6th bits are minutes (1,2,4,8,16,32)
*/
boolean[] bitsSet = new boolean[10];
/**
* Map bits to time
*/
static Map<Integer, Integer> bitsToTime = new HashMap<>();
static {
// hours
bitsToTime.put(0, 1);
bitsToTime.put(1, 2);
bitsToTime.put(2, 4);
bitsToTime.put(3, 8);
// minutes
bitsToTime.put(4, 1);
bitsToTime.put(5, 2);
bitsToTime.put(6, 4);
bitsToTime.put(7, 8);
bitsToTime.put(8, 16);
bitsToTime.put(9, 32);
}
public List<String> readBinaryWatch(int num) {
List<String> res = new ArrayList<>();
if (num < 0 || num > 10) // check constrains
return res;
backTracking(res, 0, num, 0);
Collections.sort(res);
return res;
}
/**
* The main logic
*
* @param result - result
* @param startIdx - the start idx for the loop on a new recursion invocation
* @param target - when we have to stop and add our accumulated res of bits and present it as time
* @param lvl - when we reach this lvl, we have enough accumulated data to convert it to time
*/
private void backTracking(List<String> result, final int startIdx, final int target, int lvl) {
if (lvl == target) {
String bitesToTime = getRes();
if (bitesToTime != null) // if the conditions (hours < 12 || minutes < 60) are met.
result.add(bitesToTime);
return;
}
for (int i = startIdx; i < bitsSet.length; i++) {
bitsSet[i] = true; // activate i-th before go to the recursion
/**
* i + 1 - we need to make a step from the i+1 in the recursion in order to start with the next position on the
* next invocation of this method
*
* lvl + 1 - we need to count depth of the recursion so at the appropriate time when (lvl == target) add
* accumulated data to the result
*/
backTracking(result, i + 1, target, lvl + 1);
bitsSet[i] = false; // deactivate i-th after went out of the recursion
}
}
/**
* Present bits as time if a value of it is valid.
* Not valid data is (hours >= 12 || minutes >= 60)
*
* @return return a string with data or null if data is`t valid
*/
private String getRes() {
int hours = 0;
int minutes = 0;
for (int i = 0; i < bitsSet.length; i++) {
if (bitsSet[i] && i <= 3) {
hours += bitsToTime.get(i);
} else if (bitsSet[i] && i > 3) {
minutes += bitsToTime.get(i);
}
}
if (hours >= 12 || minutes >= 60) // validate data
return null;
StringBuilder sb = new StringBuilder();
sb.append(hours).append(":");
if (minutes >= 0 && minutes < 10)
sb.append(0);
sb.append(minutes);
return sb.toString();
}
}
Solution 1
/**
* @param {number} num
* @return {string[]}
*/
var readBinaryWatch = function(num) {
var res = [];
helper(num, 0, 0, res, 0);
return res;
};
var helper = function (num, hours, minute, res, index) {
if (num < 0 || index > 10 || hours > 11 || minute > 59) {
return;
} else if (num === 0) {
res.push(hours + ':' + (minute < 10 ? ('0' + minute) : minute));
} else if (index < 4) {
helper(num - 1, hours + Math.pow(2, index), minute, res, index + 1);
helper(num, hours, minute, res, index + 1);
} else if (index >= 4) {
helper(num - 1, hours, minute + Math.pow(2, index - 4), res, index + 1);
helper(num, hours, minute, res, index + 1);
}
};
Explain:
nope.
Complexity:
- Time complexity :
- Space complexity :
Solution 2
/**
* @param {number} num
* @return {string[]}
*/
var readBinaryWatch = function(num) {
var res = [];
for (var i = 0; i < 12; i++) {
for (var j = 0; j < 60; j++) {
if (numberOfDigit(i) + numberOfDigit(j) === num) {
res.push(i + ':' + (j < 10 ? ('0' + j) : j));
}
}
}
return res;
};
var numberOfDigit = function (num) {
var n = 0;
var tmp = 0;
for (var i = 5; i >= 0; i--) {
tmp = 1 << i;
if (num >= tmp) {
n++;
num -= tmp;
}
}
return n;
};
Solution (Java)
class Solution {
public List<String> readBinaryWatch(int turnedOn) {
List<String> times = new ArrayList<>();
for (int hour = 0; hour <= 11; hour++) {
for (int minutes = 0; minutes <= 59; minutes++) {
readBinaryWatchHelper(turnedOn, times, hour, minutes);
}
}
return times;
}
private void readBinaryWatchHelper(
int turnedOn, List<String> selectedTimes, int hour, int minutes) {
if (isValidTime(turnedOn, hour, minutes)) {
selectedTimes.add(getTimeString(hour, minutes));
}
}
private String getTimeString(int hour, int minutes) {
StringBuilder time = new StringBuilder();
time.append(hour);
time.append(':');
if (minutes < 10) {
time.append('0');
}
time.append(minutes);
return time.toString();
}
private boolean isValidTime(int turnedOn, int hour, int minutes) {
int counter = 0;
while (hour != 0) {
if ((hour & 1) == 1) {
counter++;
}
hour >>>= 1;
}
if (counter > turnedOn) {
return false;
}
while (minutes != 0) {
if ((minutes & 1) == 1) {
counter++;
}
minutes >>>= 1;
}
return counter == turnedOn;
}
}
Explain:
nope.
Complexity:
- Time complexity :
- Space complexity :