Easy to understand Java BFS solution O(m),


  • 4
    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?


Log in to reply
 

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