Easy to understand Java BFS solution O(m)


  • 6
    B

    I see all are math based solutions and it is O(1).
    Here is my BFS solution to count all potential status for n bulb after m operations.

    public int flipLights(int n, int m) {
            n = n <= 6? n: (n % 6 + 6);
            
            Set<Integer> visited = new HashSet<>();
            Queue<Integer> queue = new LinkedList<>();
            int init = (1 << n) - 1;
            queue.offer(init);
            for (int i=0; i<m; i++) {
                int size = queue.size();
                visited.clear();
                for (int k=0; k<size; k++) {
                    int s = queue.poll();
                    int[] next = new int[] {flipAll(s, n), 
                         flipEven(s, n), flipOdd(s, n), flip3k1(s, n)};
                    for (int s1: next) {
                        if (!visited.contains(s1)) {
                            queue.offer(s1);
                            visited.add(s1);
                        }
                    }
                }
            }
            return queue.size();
        }
        
        private int flipAll(int s, int n) {
            int x = (1 << n) - 1;
            return s ^ x;
        }
    
        private int flipEven(int s, int n) {
            for (int i=0; i<n; i+=2) {
                s ^= 1 << i;
            }
            return s;
        }
    
        private int flipOdd(int s, int n) {
            for (int i=1; i<n; i+=2) {
                s ^= 1 << i;
            }
            return s;
        }
    
        private int flip3k1(int s, int n) {
            for (int i=0; i<n; i+=3) {
                s ^= 1 << i;
            }
            return s;
        }
    

  • 0
    R

    @buttercup said in Easy to understand Java BFS solution O(m),:

    Why is it O(m)? Isn't it O(m*queue_size) because queue_size is not a constant?


  • 0
    M

    An integer is 32-bit but n fits in range [0 1000], how could you use an integer to represent the status of 1000 bulb?


  • 0
    B

    @MinJiang
    If you look at the operations, they are operations modulo 2 and 3. So you only need consider a sequence of 6 bulbs. Every 6 bulbs in a row share same states.


  • 0
    B

    @richdalgo Queue size has a fixed upper bound. You can refer the O(1) solution.


Log in to reply
 

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