# 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.

![](/files/-LoJIjWWW6Uq5G5JPurX)

**Complexity:** O(num\_ops*4*(pow(2, lights))) time and O(4\*(pow(2, lights))) space

```cpp
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();
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/672-bulb-switcher-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.