C++ solution using Algorithm for Generating nCk Combinations.


  • 0
    D
    class Solution {
    public:
        vector<string> readBinaryWatch(int num){
            vector<string> result;
            if(num==0){
                result.push_back("0:00");
                return result;
            }
    
            auto end_combination = consecutive_number(watch_scale - num + 1, watch_scale);
            auto begin_combination = consecutive_number(1, num), combination = begin_combination;
            while(true){
                string time = read_hour_minute_from_binary_watch(combination);
                if(time != string()) {
                    result.push_back(time);
                }
    
                if(combination == end_combination){
                    break;
                }
                combination = next_combination(combination, num, watch_scale);
            }
    
            return result;
        }
    private:
            static constexpr int hour_scale = 4, minute_scale = 6, watch_scale = hour_scale + minute_scale;
            array<int, watch_scale> watch_dial{{8,4,2,1,32,16,8,4,2,1}};
    
            string time_string(int hour, int minute){
    
                string minute_str = minute<10? to_string(0)+to_string(minute): to_string(minute);
                return to_string(hour) + ":" + minute_str;
            }
    
            vector<int> consecutive_number(int begin, int end){
    
                vector<int> result;
                for(int i=begin; i<=end; i++){
                    result.push_back(i);
                }
    
                return result;
            }
    
            //The next k-element combination from {1, 2, ..., n-1, n}. This algorithm is from the textbook *Discrete Mathematics and Its Applications* by Kenneth H.Rosen
            vector<int> next_combination(vector<int>combination, int k, int n){
    
                int i = k - 1;
                while(combination[i] == n - (k - 1 - i)){
                    i -= 1;
                }
                combination[i] += 1;
                for(int j=i+1; j<k; j++){
                    combination[j] = combination[i] + j - i;
                }
    
                return combination;
            }
    
            string read_hour_minute_from_binary_watch(vector<int> combination){
    
                int hour = 0, minute = 0;
                for(auto v:combination){
                    if(v<=hour_scale){
                        hour += watch_dial[v-1];
                    }
                    else{
                        minute += watch_dial[v-1];
                    }
                }
    
                if(minute>=60 | hour>=12){
                    return string();
                }
                return time_string(hour, minute);
            }
    };
    

Log in to reply
 

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