New Problem Solution "Binary Watch"

haoel · haoel · commit 428570116115 · 2016-11-05T22:23:05.000+08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ LeetCode
 
 | # | Title | Solution | Difficulty |
 |---| ----- | -------- | ---------- |
+|401|[Binary Watch](https://leetcode.com/problems/binary-watch/) | [C++](./algorithms/cpp/binaryWatch/BinaryWatch.cpp)|Easy|
 |400|[Nth Digit](https://leetcode.com/problems/nth-digit/) | [C++](./algorithms/cpp/nthDigit/NthDigit.cpp)|Easy|
 |399|[Evaluate Division](https://leetcode.com/problems/evaluate-division/) | [C++](./algorithms/cpp/evaluateDivision/EvaluateDivision.cpp)|Medium|
 |398|[Random Pick Index](https://leetcode.com/problems/random-pick-index/) | [C++](./algorithms/cpp/randomPickIndex/RandomPickIndex.cpp)|Medium|
diff --git a/algorithms/cpp/binaryWatch/BinaryWatch.cpp b/algorithms/cpp/binaryWatch/BinaryWatch.cpp
@@ -0,0 +1,111 @@
+// Source : https://leetcode.com/problems/binary-watch/
+// Author : Hao Chen
+// Date   : 2016-11-05
+
+/*************************************************************************************** 
+ *
+ * A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 
+ * LEDs on the bottom represent the minutes (0-59).
+ * Each LED represents a zero or one, with the least significant bit on the right.
+ * 
+ * For example, the above binary watch reads "3:25".
+ * 
+ * Given a non-negative integer n which represents the number of LEDs that are 
+ * currently on, return all possible times the watch could represent.
+ * 
+ * Example:
+ * Input: n = 1Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", 
+ * "0:16", "0:32"]
+ * 
+ * Note:
+ * 
+ * The order of output does not matter.
+ * The hour must not contain a leading zero, for example "01:00" is not valid, it 
+ * should be "1:00".
+ * The minute must be consist of two digits and may contain a leading zero, for example 
+ * "10:2" is not valid, it should be "10:02".
+ ***************************************************************************************/
+
+class Solution {
+private:
+    void combination(int len, int n, int max, bool zero,
+                     int start, int k, int solution, 
+                     vector<vector<string>>& result) {
+        if (solution > max){
+            return;
+        }
+        if (k == 0) {
+            char tmp[5] = "";
+            if (zero) {
+                sprintf(tmp, "%02d", solution);
+            }else{
+                sprintf(tmp, "%d", solution);
+            }
+            result[n].push_back(tmp);
+            return;
+        }
+        for (int i=start; i<=len-k; i++) {
+            solution += pow(2, i);
+            combination(len, n, max, zero, i+1, k-1, solution, result);
+            solution -= pow(2, i);
+        }
+    }
+    
+    void generate_combination(int nLED, int max, bool zero, vector<vector<string>>& result) {
+        for (int i=0; i<nLED; i++) {
+            combination(nLED, i, max, zero, 0, i, 0, result);
+        }
+    }
+    
+    void print(vector<vector<string>>&  vv) {
+        for(auto v : vv) {
+            cout << "[ ";
+            for (auto i : v) {
+                cout << i << " ";
+            }
+            cout << "]" << endl;
+        }
+    }
+    
+private:
+    vector<vector<string>> hour;
+    vector<vector<string>> mins;
+
+public:
+
+    Solution():hour(4, vector<string>()), mins(6, vector<string>()){
+        generate_combination(4, 11, false, hour);
+        //print(hour);
+        //[ 0 ]
+        //[ 1 2 4 8 ]
+        //[ 3 5 9 6 10 ]
+        //[ 7 11 ]
+        
+        
+        generate_combination(6, 59, true, mins);
+        //print(mins);
+        //[ 00 ]
+        //[ 01 02 04 08 16 32 ]
+        //[ 03 05 09 17 33 06 10 18 34 12 20 36 24 40 48 ]
+        //[ 07 11 19 35 13 21 37 25 41 49 14 22 38 26 42 50 28 44 52 56 ]
+        //[ 15 23 39 27 43 51 29 45 53 57 30 46 54 58 ]
+        //[ 31 47 55 59 ]        
+    }
+    
+    vector<string> readBinaryWatch(int num) {
+        
+        vector<string> result;
+        for (int i = 0; i <= 3 && i <= num; i++) {
+            if (num - i > 5) {
+                continue;
+            }
+            for (auto h : hour[i]) {
+                for (auto m : mins[num - i]) {
+                    result.push_back( h + ":" + m );
+                }
+            }
+            
+        }
+        return result;
+    }
+};
