Solution by awice


  • 0

    Approach #1: Brute Force with Optimizations [Accepted]

    Intuition

    Naively, the number of operations is $$4^m$$, and the number of light-states is $$2^n$$. These are way too big, so we focus on heuristics that can reduce the size of these spaces that we want to search on.

    Algorithm

    Suppose we did f[0] of the first operation, f[1] of the second, f[2] of the third, and f[3] of the fourth, where sum(f) == m.

    First, all these operations commute: doing operation A followed by operation B yields the same result as doing operation B followed by operation A. So we only care about the quantity of each operation.

    Secondly, when it comes to the state of the lights, doing operation A followed by operation A again is the same as doing nothing. So really, we only needed to know the residues cand[i] = f[i] % 2. There are only 16 different possibilities for the residues in total, so we can try them all.

    We'll loop cand through all 16 possibilities (0, 0, 0, 0), (0, 0, 0, 1), ..., (1, 1, 1, 1), but not all of them necessarily occur. cand occurs only if there is some f with sum(f) == m and cand[i] = f[i] % 2.

    The necessary and sufficient condition to find such an f is sum(cand) % 2 == m % 2 and sum(cand) <= m. With exactly m operations, we must spend sum(cand) operations doing the operations indicated by cand; then as long as we have an even number of operations left over, we can keep doing operation 1; and if we don't have an even number of operations left over, we can't make cand as desired.

    Also, we can set n = min(n, 6). We only need to care about the first 6 lights, as the 6k+ith light is equal to the i-th light. This is because the first operation repeats every 1 light, the second and third operations repeat every 2 lights, and the fourth operation repeats every 3 lights; hence, no matter what operations are applied, the lights will repeat every $\text{lcm}(1, 2, 2, 3) = 6$ lights.

    Java

    class Solution {
        public int flipLights(int n, int m) {
            n = Math.min(n, 6);
            Set<Integer> seen = new HashSet<Integer>();
            for (int cand = 0; cand < 1<<4; cand++) {
                if (Integer.bitCount(cand) <= m &&
                        Integer.bitCount(cand) % 2 == m % 2) {
                    int lights = 0b111111;
                    if ((cand>>0) %2 > 0) lights ^= 0b111111;
                    if ((cand>>1) %2 > 0) lights ^= 0b010101;
                    if ((cand>>2) %2 > 0) lights ^= 0b101010;
                    if ((cand>>3) %2 > 0) lights ^= 0b100100;
                    seen.add(lights >> (6-n));
                }
            }
            return seen.size();
        }
    }
    

    Python

    def flipLights(self, n, m):
        seen = set()
        for cand in itertools.product((0, 1), repeat = 4):
            if sum(cand) % 2 == m % 2 and sum(cand) <= m:
                lights = []
                for i in xrange(min(n, 6)):
                    light = 1
                    light ^= cand[0]
                    light ^= cand[1] and i % 2
                    light ^= cand[2] and i % 2 == 0
                    light ^= cand[3] and i % 3 == 0
                    lights.append(light)
                seen.add(tuple(lights))
    
        return len(seen)
    

    Complexity Analysis

    • Time Complexity: $$O(1)$$. For each of 16 possibilities for cand, we do $$O(min(n, 6)) = O(1)$$ work.

    • Space Complexity: $$O(1)$$. The size of seen is bounded by 16 - one for each candidate sequence of residues cand.


    Approach #2: Mathematical [Accepted]

    Intuition

    As in Approach #1, we only need to consider $$n \leq 6$$. Also, when $$m \geq 3$$, all candidate residues cand are valid as defined in Approach #1. Thus, we only need to consider the space $$m \leq 3, n \leq 6$$ - a space small enough to brute force.

    Algorithm

    Actually, we may take n = min(n, 3). If the operations are a, b, c, d, then modulo 2:

    • Light 1 = Light 7 = ... = 1 + a + c + d
    • Light 2 = Light 8 = ... = 1 + a + b
    • Light 3 = Light 9 = ... = 1 + a + c
    • Light 4 = Light 10 = ... = 1 + a + b + d
    • Light 5 = Light 11 = ... = 1 + a + c
    • Light 6 = Light 12 = ... = 1 + a + b

    So that (modulo 2):

    • Light 4 = (Light 1) + (Light 2) + (Light 3)
    • Light 5 = Light 3, and
    • Light 6 = Light 2.

    which shows that knowing the first 3 lights is enough to determine all the remaining lights in the sequence.

    Now, we can do casework on m. The transitions made by the operations a, b, c, d are to XOR by (1, 1, 1), (0, 1, 0), (1, 0, 1), or (1, 0, 0) respectively.

    • If m = 0, there is only one state (1, 1, 1).
    • If m = 1, then we could get (0, 0, 0), (1, 0, 1), (0, 1, 0), (0, 1, 1).
    • If m = 2, with some effort we can get all 8 possibilities except (0, 1, 1).
    • If m = 3, we can get every possibility.

    This reduced the problem to knowing the answer for m <= 3, n <= 3. The final answer is shown below.

    Java

    class Solution {
        public int flipLights(int n, int m) {
            if (m == 0) return 1;
            if (n == 1) return 2;
            if (n == 2) return m == 1 ? 3 : 4;
            return m == 1 ? 4 : m == 2 ? 7 : 8;
        }
    }
    

    Complexity Analysis

    • Time and Space Complexity: $$O(1)$$.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.