Java Bit manipulation and Backtracking method. Easy to understand.


  • 0
    M
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> res = new ArrayList<>();
            backtrack(0, num, 0, res);
            return res;
        }
        public void backtrack(int start, int numOfOnes, int curr, List<String> res) {
            if(numOfOnes == 0) {
                String time = numToTimeString(curr);
                if(time != null) res.add(time);            
            }
            else {
                for(int i = start; i <= 11 - numOfOnes; i++) {
                    // set ith bit from right to 1
                    curr |= 1 << i;
                    backtrack(i+1, numOfOnes - 1, curr, res);
                    // remove that 1 set above
                    curr ^= 1 << i;
                }
            }
        }
        private String numToTimeString(int num) {
            // last 4 bits : hours
            // first 6 bits : minutes
            if((num & 0b1111) > 11) return null;
            String hour = (num & 0b1111) + "";
            if((num >>> 4) > 59) return null;
            String mins = (num >>> 4) + "";
            if(mins.length() == 1) mins = "0" + mins;
            return hour + ":" + mins;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.