C++ solution using bit vectors and permutations


  • 0
    S
    
    class Solution {
    public:
        vector<string> readBinaryWatch(int num) {
            vector<string> result;
            vector<int> possible_values;
            possibleList(BITS_NUMBER, num, 0, possible_values);
            for (auto decor: possible_values){
                result.push_back(toStringDecor(decor));
            }
            return result;
        }
        
    private:
        int HOUR_SHIFT = 6;
        int MINUTE_MASK = 64 - 1;
        int BITS_NUMBER = 10;
        
        void possibleList(const int num_of_bits,
                                 const int num_of_ones_left, int result_number, vector<int> &result_list);
        string toStringDecor(const int decor);
    };
    
    
    void Solution::possibleList(const int num_of_bits,
                                       const int num_of_ones_left, int result_number, vector<int> &result_list){
        if ((result_number >> HOUR_SHIFT) < 12) {
            if (num_of_bits == 0) {
                if ((result_number & MINUTE_MASK) < 60){
                    result_list.push_back(result_number);
                }
            }
            if (num_of_bits - 1 >= num_of_ones_left) {
                possibleList(num_of_bits - 1, num_of_ones_left, result_number, result_list);
            }
            
            if (num_of_ones_left > 0) {  // If we have any 1s left to place
                possibleList(num_of_bits - 1, num_of_ones_left - 1, result_number | (1 << (num_of_bits - 1)), result_list);
            }
        }
    }
    
    string Solution::toStringDecor(const int decor){
        int hour = decor >> HOUR_SHIFT;
        int minute = decor & MINUTE_MASK;
        return to_string(hour) + ":" + (minute < 10 ? "0" + to_string(minute) : to_string(minute));
    }
    
    

Log in to reply
 

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