Annotated C++ solution calculating all LED permutations


  • 0
    K
    class Solution {
    private:
    // this function returns an exhaustive list of permutations of _m_ elements in _n_ "buckets"
    // because the space of this problem is limited to 6 elements max we enumerate the permutations
    //  with integer numbers (plenty of space even with 32 bits)
    // the main loop starts with the first _m_ bits set to 1 (the rest are 0s)
    // then it shifts the most significant bit (MSB) sequentially over the remaining _n_-_m_
    //  positions and makes a recursive call on a smaller subproblem bounded by the current
    //  position of the MSB and permuting the remaining _m_-1 bits
    
    vector<int> NchooseM(int n, int m){
        vector<int> retval;
        if( n==0 ){ retval.push_back(0); return retval; }
        if( m==0 ){ retval.push_back(0); return retval; }
        if( n==m ){ retval.push_back((1<<n)-1); return retval; }
    
        // start with _m_th element in its initial m-1 position and shift is to the last n-1 "bucket"
        for(int pos=m-1; pos<n; pos++){
            // solve smaller problem with _m_-1 elements permuted in _pos_ "buckets"
            vector<int> sub = NchooseM(pos,m-1);
            // note the current MSB position
            for(auto i: sub)
                retval.push_back( (1<<pos) + i );
        }
        return retval;
    }
    
    // make short Look Up Tables for fast conversion of the limited number of cases here
    const char* hourToString(int i){
        if( i<0 || i>11 ) return 0;
        const char *hours[] = {"0","1","2","3","4","5","6","7","8","9","10","11"};
        return hours[i];
    }
    
    const char* minToString(int i){
        if( i<0 || i>59 ) return 0;
        const char *minutes[] = {
               "00","01","02","03","04","05","06","07","08","09",
               "10","11","12","13","14","15","16","17","18","19",
               "20","21","22","23","24","25","26","27","28","29",
               "30","31","32","33","34","35","36","37","38","39",
               "40","41","42","43","44","45","46","47","48","49",
               "50","51","52","53","54","55","56","57","58","59"
        };
        return minutes[i];
    }
    
    public:
    vector<string> readBinaryWatch(int num) {
        vector<string> retval;
        // safety check
        if( num > 10 ) return retval;
        // split num LEDs between hours and minutes
        for(int h=( num-6<=0 ? 0 : num-6 ); h<=4 && h<=num; h++){
            // at this point we have a fixed number of LEDs for representing hours (h) and minutes (num-h)
            // now generate all NchooseM combinations for hours and minutes and combine
            vector<int> hours = NchooseM(4,h);
            vector<int> mins  = NchooseM(6,num-h);
            for(auto hh: hours)
                for(auto mm: mins){
                    if( hh<12 && mm<60 )
                        retval.push_back( string(hourToString(hh)) + ":" + minToString(mm) );
                }
        }
        return retval;
    }
    

    };


Log in to reply
 

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