672 Bulb Switcher II

There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.

Suppose n lights are labeled as number [1, 2, 3 ..., n], function of these 4 buttons are given below:

1. Flip all the lights.

2. Flip lights with even numbers.

3. Flip lights with odd numbers.

4. Flip lights with (3k + 1) numbers, k = 0, 1, 2, ...

Example 1:

Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]

Example 2:

Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]

Example 3:

Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].

Note: n and m both fit in range [0, 1000].

The Idea: I decided to go with a sort of BF approach with minor optimizations to make it become accepted within the limited time frame. Essentially, I built a tree that presented all the unique possible states without any redundancies. Avoiding these redundancies ensured that the time complexity would be < O(4^n) where n is the number of operations. To avoid redundancies I used an unordered_set that ensured that I would only branch of from unique states. Therefore the most I can ever expect to branch from per level will stay bounded by a constant.

Complexity: O(num_ops4(pow(2, lights))) time and O(4*(pow(2, lights))) space

struct VectorHash {
    size_t operator()(const std::vector<bool>& v) const {
        std::hash<bool> hasher;
        size_t seed = 0;
        for (bool i : v) {
            seed ^= hasher(i) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }
        return seed;
    }
};

auto toggle_all = [&](const vector<bool> &lights) {
    vector<bool> toggled = lights;
    for (int i = 0; i < toggled.size(); i++) {
        toggled[i] = !toggled[i];
    }
    return toggled;
};

auto toggle_even = [&](const vector<bool> &lights) {
    vector<bool> toggled = lights;
    for (int i = 0; i < toggled.size(); i++) {
        if (i % 2 == 0)
            toggled[i] = !toggled[i];
    }
    return toggled;
};

auto toggle_odd = [&](const vector<bool> &lights) {
    vector<bool> toggled = lights;
    for (int i = 0; i < toggled.size(); i++) {
        if (i % 2 != 0)
            toggled[i] = !toggled[i];
    }
    return toggled;
};

auto toggle_3k_plus_1 = [&](const vector<bool> &lights) {
    vector<bool> toggled = lights;
    int k = 0;
    int f_x = (3 * k) + 1;
    while(f_x < toggled.size()) {
        toggled[k] = !toggled[k];
        f_x = (3 * ++k) + 1;
    }
    return toggled;
};

int flipLights(int lights, int ops) {
    if (lights > 0 && ops == 0) return 1;
    else if (lights == 0) return 0;

    queue<pair<vector<bool>, bool>> q;
    unordered_set<vector<bool>, VectorHash> cur_lvl;
    cur_lvl.reserve(pow(2, lights));
    vector<function<vector<bool>(vector<bool> &)>> rotations = 
        { toggle_all, toggle_even, toggle_odd, toggle_3k_plus_1 };

    q.push({ vector<bool>(lights, 1), false });
    q.push({ vector<bool>(), true });

    while (ops >= 1) {
        auto front = q.front(); q.pop();

        if (!front.second) {
            for (auto functor : rotations) {
                vector<bool> next = functor(front.first);
                if (cur_lvl.find(next) == cur_lvl.end()) {
                    q.push({ next, false });
                    // control at most 4*(pow(2, lights)) in unordered_set
                    cur_lvl.insert(next); 
                }
            }
        }
        else {
            --ops; 
            if (ops >= 1) {
                cur_lvl.clear();
                cur_lvl.reserve(pow(2, lights));
                q.push({ vector<bool>(), true });
            }
        }
    }

    return cur_lvl.size();
}