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:
Flip all the lights.
Flip lights with even numbers.
Flip lights with odd numbers.
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();
}
