LeetCode: Binary Watch

This one was a little more sophisticated, but still marked by LeetCode as an easy category problem. Here it is: https://leetcode.com/problems/binary-watch/. The goal is, given a number of potential lights to be on in the following binary watch, list all the possible hours it can give.


Problem will be split primarily into two parts:

  • Part 1: model a configuration for the clock. In my case I decided to model it as one string with 10 chars, with 0s (off) or 1s (on), the first 4 chars indicating the hour, the last 6 the minutes. Hence for the config in the picture the string would then be "0011011001". Write a method to determine the time given a single config. The method is basically a base-conversion algorithm from base-2 to base-10 with some minor (albeit important) caveats along the way. But that's primarily what part 1 does: a base conversion.
  • Part 2: do a DFS (depth-first-search) generating all the possible values of config, turning on the bits whenever doable. Don't worry about time complexity: a 2^10 is a mere 1024. Along the way call the base converter in part 1 at the base case, add it to the list, return (remember that the order doesn't matter). No need to worry about dupes, if the base case and induction cases are correct there won't be any dupes.
Code is below, cheers, Marcelo.


    public class Solution
    {
        public IList<string> ReadBinaryWatch(int num)
        {
            List<string> listWithResults = new List<string>();
            ReadBinaryWatchHelper(num, 0, "", listWithResults);
            return listWithResults;
        }

        private void ReadBinaryWatchHelper(int currentNum,
                                           int currentPosition,
                                           string config,
                                           IList<string> listWithResults)
        {
            if (currentPosition == 10 &&
                currentNum == 0)
            {
                string time = TimeGivenConfig(config);
                if (time != "")
                {
                    listWithResults.Add(time);
                }
                return;
            }
            else if (currentPosition == 10)
            {
                return;
            }

            if (currentNum > 0)
            {
                ReadBinaryWatchHelper(currentNum - 1, currentPosition + 1, config + "1", listWithResults);
            }
            ReadBinaryWatchHelper(currentNum, currentPosition + 1, config + "0", listWithResults);
        }

        private string TimeGivenConfig(string config)
        {
            //Hour
            string hour = config.Substring(0, 4);
            int h = 0;
            int power = 1;
            for (int i = hour.Length - 1; i >= 0; i--)
            {
                h += (hour[i] == '0') ? 0 : power;
                power *= 2;
            }

            if (h >= 12) return "";

            //Minute
            string minute = config.Substring(4);
            int m = 0;
            power = 1;
            for (int i = minute.Length - 1; i >= 0; i--)
            {
                m += (minute[i] == '0') ? 0 : power;
                power *= 2;
            }

            if (m >= 60) return "";

            string retVal = "";

            retVal += h.ToString();
            retVal += ":";
            if (m < 10)
            {
                retVal += "0";
            }
            retVal += m.ToString();

            return retVal;
        }
    }

Comments

  1. Given that the range for valid numbers is so limited (just 10 bits) it's possible to quickly loop through the entire range and note everything that satisfies our requirements. The naive implementation is below:

    class Solution {
    private:
    const int MINUTES_MASK = 0b111111;

    int bit_count(int n) {
    char count = 0;
    for (; n > 0; ++count) n = n & (n - 1);
    return count;
    }
    public:
    vector readBinaryWatch(int num) {
    vector times;
    for (int i = 0; i < (1 << 10); ++i) {
    int hours = i >> 6;
    int minutes = i & MINUTES_MASK;
    if (hours < 12 && minutes < 60 && bit_count(i) == num) {
    times.emplace_back(to_string(hours) + ":" + (minutes < 10 ? "0" : "") + to_string(minutes));
    }
    }
    return times;
    }
    };

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Changing the root of a binary tree

Prompt Engineering and LeetCode

ProjectEuler Problem 719 (some hints, but no spoilers)