O(1) Java bit operation


  • 0
    F

    Java O(1) solution:

    Explain:

    • for n > 3, result is same as n = 3, if same series of operations apply on 3 bulbs generate k distinct result, apply them on more than 3 bulbs would also generate k distinct result.
    • only even and odd matters for each operation. So the total possible op series would be [0,0,0,0], [0,0,0,1]...to [1,1,1,1], 16 total
    • order of operations doesn't matter
    public int flipLights(int n, int m) {
            int odd = 0b101;
            int even = 0b010;
            int three = 0b001;
            if (n > 3) n = 3;
            Set<Integer> res = new HashSet<>();
            for (int i = 0; i < 16; ++i) {
                int cnt = 0;
    
                for (int k = 0; k < 4; ++k) if ((i&(1<<k)) != 0)++cnt;
                if (cnt % 2 != m % 2 || m < cnt) continue;
                int v = (1 << n) - 1;
                int mask = v;
                if ((i & 1) != 0) v = ~v;
                if ((i & 2) != 0) v = even&~v|v&~even;
                if ((i & 4) != 0) v = odd&~v|v&~odd;
                if ((i & 8) != 0) v = three&~v|v&~three;
                res.add(v&mask);
            }
            return res.size();
        }
    

  • 0
    D
    This post is deleted!

  • 0
    F

    @donggua_fu add more details and replace the magic constants with binary literals


  • 0
    D

    @feng.peng.3597 enen, I almost got the idea..Thank you so much~~(^_^)


Log in to reply
 

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