Bulb Switcher II Solutions in C++

/// Source : https://leetcode.com/problems/bulb-switcher-ii/description/
/// Author : liuyubobobo
/// Time   : 2017-12-02

#include <iostream>
#include <unordered_set>

using namespace std;

/// We can see the first six bulb status can decide all the sequence
/// So we can try all 2^4 operations and see how many status are there
/// for the first six bulb
///
/// Time Complexity: O(2^4)
/// Space Complexity: O(1)
class Solution {
public:
    int flipLights(int n, int m) {

        unordered_set<int> states;
        n = min(n, 6);
        for(int i = 0; i < 16 ; i++){
            int state = 0b111111;

            int onebit = onenum(i, 4);
            if(onebit > m || m % 2 != onebit % 2)
                continue;

            if(i&1)
                state ^= 0b111111;
            if(i&2)
                state ^= 0b101010;
            if(i&4)
                state ^= 0b010101;
            if(i&8)
                state ^= 0b001001;

            states.insert(state&((1<<n)-1));
        }

        return states.size();
    }

private:
    int onenum(int x, int bitnum){
        int res = 0;
        for(int i = 0 ; i < bitnum ; i ++)
            if(x&(1<<i))
                res ++;
        return res;
    }
};

int main() {

    cout << Solution().flipLights(1, 1) << endl;
    cout << Solution().flipLights(2, 1) << endl;
    cout << Solution().flipLights(3, 1) << endl;
    cout << Solution().flipLights(3, 3) << endl;
    cout << Solution().flipLights(3, 2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/bulb-switcher-ii/description/
/// Author : liuyubobobo
/// Time   : 2017-12-02

#include <iostream>
#include <unordered_set>

using namespace std;

/// For further analysis, we can see the first three lights uniquely determine the rest of the sequence
/// Assume the four operation is a, b, c, d, then:
/// - Light 1 = 1 + a + c + d
/// - Light 2 = 1 + a + b
/// - Light 3 = 1 + a + c
/// - Light 4 = 1 + a + b + d
/// - Light 5 = 1 + a + c
/// - Light 6 = 1 + a + b
///
/// so that (module 2)
/// - Light 4 = (Light 1) + (Light 2) + (Light 3)
/// - Light 5 = Light 3
/// - Light 6 = Light 2
///
/// so there's just 8 cases, we can enumerate all these 8 cases and get the result.
///
/// Time Complexity: O(1)
/// Space Complexity: O(1)
class Solution {
public:
    int flipLights(int n, int m) {

        n = min(n, 3);
        if (m == 0) return 1;
        if (m == 1) return n == 1 ? 2 : n == 2 ? 3 : 4;
        if (m == 2) return n == 1 ? 2 : n == 2 ? 4 : 7;
        return n == 1 ? 2 : n == 2 ? 4 : 8;
    }
};

int main() {

    cout << Solution().flipLights(1, 1) << endl;
    cout << Solution().flipLights(2, 1) << endl;
    cout << Solution().flipLights(3, 1) << endl;
    cout << Solution().flipLights(3, 3) << endl;
    cout << Solution().flipLights(3, 2) << endl;

    return 0;
}