IVN
0%

Bit

Posted on Edited on In
Symbols count in article: 14k Reading time ≈ 13 mins.

Bit/Bit_Mask好题

137. Single Number II

@kenanlv the part about XOR is often supposed to be textbook knowledge because of well-known swap implementation without tmp variable:

1
2
3
a = a^b      # mix of a and b
b = a^b      # a^b^b = a
a = a^b      # a^b^a = b

If you don’t know that idea, the interviewer would probably simplify the task, asking you first to solve the problem “each element appears twice except one, find that one.” That is a very straightforward XOR usage, like in swap above

1
seen_once = seen_once^num

Once you’ll figure that out, to go to the idea of two bitmasks instead of one is not a big deal, basically it’s

NOT seen_twice AND (CHANGE see_once)
NOT seen_once AND (CHANGE see_twice)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public int singleNumber(int[] nums) {
    int seenOnce = 0, seenTwice = 0;

    for (int num : nums) {
      // first appearence: 
      // add num to seen_once 
      // don't add to seen_twice because of presence in seen_once

      // second appearance: 
      // remove num from seen_once 
      // add num to seen_twice

      // third appearance: 
      // don't add to seen_once because of presence in seen_twice
      // remove num from seen_twice
      seenOnce = ~seenTwice & (seenOnce ^ num);
      seenTwice = ~seenOnce & (seenTwice ^ num);
    }

    return seenOnce;
  }
}

开背！

1
2
3
4
5
6
7
8
9
public int singleNumber(int[] nums) {
    int seenOnce=0;
    int seenTwice=0;
    for (int num : nums) {
        seenOnce=(~seenTwice) & (seenOnce^num);
        seenTwice=(~seenOnce) & (seenTwice^num);
    }
    return seenOnce;
}

260. Single Number III

The bitmask will have all the differences between x and y (the two singles). x has 0 and y has 1 or vice-versa in those bits. You take one difference, the rightmost one.
Iterate through array again dividing into two. The ones which has 1 on the rightmost different bit into one group and those who have 0 into another group.
Group1 : [x^a^a^b^b] = x
Group2 : [y^c^c^d^d] = y
bitmask^x = y;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
  public int[] singleNumber(int[] nums) {
    // difference between two numbers (x and y) which were seen only once
    int bitmask = 0;
    for (int num : nums) bitmask ^= num;

    // rightmost 1-bit diff between x and y
    int diff = bitmask & (-bitmask);

    int x = 0;
    // bitmask which will contain only x
    for (int num : nums) if ((num & diff) != 0) x ^= num;

    return new int[]{x, bitmask^x};
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] singleNumber(int[] nums) {
    int ab=0;
    for (int num : nums) {
        ab^=num;
    }
    //ab=a^b
    int r=ab&(-ab);
    int a=0;
    for (int num : nums) {
        if((num&r)!=0){
            a^=num;
        }
    }
    return new int[]{a,ab^a};
}

191. Number of 1 Bits

1
2
3
4
5
6
7
8
9
public int hammingWeight(int n) {
    int count=0;
    while(n!=0){
        count+=n&1;
        //must use logical shift, not arithmetic shift
        n>>>=1; //n>>=1则不行
    }
    return count;
}

338. Counting Bits

Follow up:

  • It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//0
//1
//10
//11
//100
//101
//110
//111
public int[] countBits(int n) {
    int[] res=new int[n+1];
    for (int i = 1; i <= n; i++) {
        res[i]=res[i>>1]+(i&1);
    }
    return res;
}

89. Gray Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public List<Integer> grayCode(int n) {
    Set<Integer> set=new HashSet<>();
    List<Integer> res=new ArrayList<>();
    res.add(0);
    set.add(0);
    int size=(int)Math.pow(2,n);
    int cur=0;
    for(int i=1; i<size; i++){
        for (int j = 0; j < n; j++) {
            //use xor (1<<j) to flip one bit
            int next=cur^(1<<j);
            if(!set.contains(next)){
                set.add(next);
                res.add(next);
                cur=next;
                break;
            }
        }
    }
    return res;
}

371. Sum of Two Integers

1
2
3
4
5
6
7
8
9
public int getSum(int a, int b) {
    while(b!=0){
        int answer=a^b;
        int carry=(a&b)<<1;
        a=answer;
        b=carry;
    }
    return a;
}

1506. Find Root of N-Ary Tree

注意：

  • Each node has a unique value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Node findRoot(List<Node> tree) {
        Set<Integer> set=new HashSet<>();
        for (Node node : tree) {
            for (Node child : node.children) {
                set.add(child.val);
            }
        }
        for (Node node : tree) {
            if(!set.contains(node.val)){
                return node;
            }
        }
        return null;
}

Follow up:

  • Could you solve this problem in constant space complexity with a linear time algorithm?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public Node findRoot(List<Node> tree) {
    int num=0;
    for (Node node : tree) {
        if(node.children.isEmpty()){
            continue;
        }
        num^=node.val;
        for (Node child : node.children) {
            if(!child.children.isEmpty()){
                num^=child.val;
            }
        }
    }
    for (Node node : tree) {
        if(node.val==num){
            return node;
        }
    }
    return tree.get(0);
}

1680. Concatenation of Consecutive Binary Numbers

Approach 1: Change to Binary String

concatenate -> <<1

1
2
3
4
5
6
7
8
9
10
11
12
public int concatenatedBinary(int n) {
    int mod=(int)1e9+7;
    long res=0;
    for (int i = 1; i <= n; i++) {
        String s=Integer.toBinaryString(i);//O(logn)
        for (int j = 0; j < s.length(); j++) {
            res=res*2+s.charAt(j)-'0';
            res%=mod;
        }
    }
    return (int)res;
}

Approach 3: Math (Bitwise Operation)

1404. Number of Steps to Reduce a Number in Binary Representation to One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.math.BigInteger;

public class LeetCode1404 {
    public int numSteps(String s) {
        BigInteger num=new BigInteger(s,2);
        BigInteger one=new BigInteger("1");
        BigInteger two=new BigInteger("2");
        int res=0;
        while(!num.equals(one)){
            //判断BigInteger的奇偶性
            if(num.testBit(0)){
                num=num.add(one);
            }else{
                num=num.divide(two);
            }
            res++;
        }
        return res;
    }
}

1318. Minimum Flips to Make a OR b Equal to c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public int minFlips(int a, int b, int c) {
    String s1=convert(a);
    String s2=convert(b);
    String s3=convert(c);
    int res=0;
    for (int i = 0; i < 32; i++) {
        int c1=s1.charAt(i)-'0';
        int c2=s2.charAt(i)-'0';
        int c3=s3.charAt(i)-'0';
        int or=c1|c2;
        if(or==c3){//0 0, 1 1
            continue;
        }
        if(or==0 && c3==1){//0 1
            res++;
        }else if(c1==1 && c2==1){
            res+=2;
        }else{
            res++;
        }
    }
    return res;
}

private String convert(int a){
    String s=Integer.toBinaryString(a);
    StringBuilder sb=new StringBuilder();
    while(sb.length()+s.length()<32){
        sb.append(0);
    }
    sb.append(s);
    return sb.toString();
}

2680. Maximum OR

Bit + Greedy

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public long maximumOr(int[] nums, int k) {
    long res=0;
    long base=0;
    long backup=0; //at least 2 occurrences for each 1 bit
    for (int num : nums) {
        backup|=base&num;
        base|=num;
    }
    //long: 10^19, no overflow
    for (int num : nums) {
        res=Math.max(res,(base^num)|backup|(long)num<<k);
    }
    return res;
}

2741. Special Permutations

dp + bit mask: using bit masks to present dp states

https://leetcode.com/problems/special-permutations/discuss/3650431/Easy-BitMask-DP-with-explanation-of-overlapping-or-Top-Down-or-C%2B%2B-beats-100-100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//overlapping subproblems in permutation? !
// nums=[3,6,9,36]
// [3,6,9,36] , pre=9, mask=1110
// [6,3,9,36] , pre=9, mask=1110

int[][] dp;
int n;
int mod=(int)1e9+7;
public int specialPerm(int[] nums) {
    dp=new int[14][16384];
    for (int[] arr : dp) {
        Arrays.fill(arr,-1);
    }
    n=nums.length;
    int res=0;
    for (int i = 0; i < n; i++) {
        res=(res+dfs(nums,1,i,1<<i))%mod;
    }
    return res;
}

private int dfs(int[] nums, int size, int pre, int mask){
    if(size==n){
        return 1;
    }
    if(dp[pre][mask]!=-1){
        return dp[pre][mask];
    }
    dp[pre][mask]=0;
    for (int i = 0; i < n; i++) {
        if((mask & (1<<i))!=0){
            continue;
        }
        if(nums[pre]%nums[i]==0 || nums[i]%nums[pre]==0){
            dp[pre][mask]=(dp[pre][mask]+dfs(nums,size+1,i,mask|(1<<i)))%mod;
        }
    }
    return dp[pre][mask];
}

464. Can I Win

思考：

  • be sensitive when seeing “permutation”, “draw from a common pool without replacement” => DP with BitMask!
  • notice when seeing target <=0,
    • if it is the first round, current player wins;
    • else current player loses.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Map<Integer,Boolean> memo=new HashMap<>();
int n;
int target;
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
    n=maxChoosableInteger;
    target=desiredTotal;
    int sum=(1+n)*n/2;
    if(target<=0){
        return true;
    }
    if(sum<target){
        return false;
    }
    return dfs(0,target);
}

private boolean dfs(int mask, int target){
    if(target<=0){
        return false;
    }
    if(memo.containsKey(mask)){
        return memo.get(mask);
    }
    boolean res=false;
    for (int i = 1; i <= n; i++) {
        if((mask&(1<<i))==0){
            if(!dfs(mask|(1<<i),target-i)){
                res=true;
                break;
            }
        }
    }
    memo.put(mask,res);
    return res;
}

1125. Smallest Sufficient Team

backtracking, TLE

36/38

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
List<Integer> res=null;
int n;
int len;
Map<String,Integer> map=new HashMap<>();
List<Integer> list=new ArrayList<>();
String[] req_skills;
List<List<String>> people;
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
    n= req_skills.length;
    len=people.size();
    this.req_skills=req_skills;
    this.people=people;
    backtracking(0);
    int[] arr=new int[res.size()];
    for (int i = 0; i < arr.length; i++) {
        arr[i]=res.get(i);
    }
    return arr;
}

private void backtracking(int cur){
    if(map.size()==n){
        if(res==null || res.size()>list.size()){
            res=new ArrayList<>(list);
        }
        return;
    }
    if(cur==len || res!=null && list.size()>=res.size()){
        return;
    }
    for (int i = cur; i < len; i++) {
        if(useful(i)){
            for (String s : people.get(i)) {
                map.put(s,map.getOrDefault(s,0)+1);
            }
            list.add(i);
            backtracking(i+1);
            list.remove(list.size()-1);
            for (String s : people.get(i)) {
                int val=map.get(s);
                if(val==1){
                    map.remove(s);
                }else{
                    map.put(s,val-1);
                }
            }
        }
    }
}

private boolean useful(int i){
    for (String s : people.get(i)) {
        if(!map.containsKey(s)){
            return true;
        }
    }
    return false;
}

DP with bitmask

注意：

  • 1 <= req_skills.length <= 16

https://leetcode.com/problems/smallest-sufficient-team/discuss/334572/JavaC%2B%2BPython-DP-Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
       int n = req_skills.length, m = people.size();
       HashMap<String, Integer> skill_index = new HashMap<>();
       for (int i = 0; i < n; ++i)
           skill_index.put(req_skills[i], i);
       List<Integer>[] dp = new List[1 << n];
       dp[0] = new ArrayList<>();
       for (int i = 0; i < m; ++i) {
           int cur_skill = 0;
           for (String s : people.get(i))
               cur_skill |= 1 << skill_index.get(s);
           for (int prev = 0; prev < dp.length; ++prev) {
               if (dp[prev] == null) continue;
               int comb = prev | cur_skill;
               if (dp[comb] == null || dp[prev].size() + 1 < dp[comb].size()) {
                   dp[comb] = new ArrayList<>(dp[prev]);
                   dp[comb].add(i);
               }
           }
       }
    //use Stream to turn List into Array
    //Arrays.stream();	List.stream()
       return dp[(1 << n) - 1].stream().mapToInt(i -> i).toArray();
   }

465. Optimal Account Balancing

https://leetcode.com/problems/optimal-account-balancing/solution/

backtracking/recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//-4,-2,2,2,2
//0,-2,-2,2,2
//

public int minTransfers(int[][] transactions) {
    //-4,-2,2,2,2
    Map<Integer,Integer> map=new HashMap<>();
    for (int[] arr : transactions) {
        map.put(arr[0],map.getOrDefault(arr[0],0)-arr[2]);
        map.put(arr[1],map.getOrDefault(arr[1],0)+arr[2]);
    }
    List<Integer> list=new ArrayList<>();
    for (Integer key : map.keySet()) {
        if(map.get(key)!=0){
            list.add(map.get(key));
        }
    }
    int[] arr=list.stream().mapToInt(i->i).toArray();
    return dfs(arr,arr.length,0);
}


private int dfs(int[] arr, int n, int cur){
    while(cur<n && arr[cur]==0){
        cur++;
    }
    if(cur==n){
        return 0;
    }
    int asset=arr[cur];
    int res=Integer.MAX_VALUE;
    for(int i=cur+1; i<n; i++){
        //0 or same sign, no transaction make sense
        if(arr[i]*asset>=0){
            continue;
        }
        //else, try to resolve cur by i
        arr[i]+=asset;
        //[0,cur] is all resolved (==0)
        res=Math.min(res,1+dfs(arr,n,cur+1));
        arr[i]-=asset;
    }
    return res;
}

DP with bitmask

思路：

  • n non-zero balance, each settles with ACH, needs at most n transactions

  • Let one of the people at act as Clearing House, other n-1 settles via him with n-1 transactions. Since the total sum is 0, settling other n-1 with automatically settle this Clearing House guy as well. needs at most n-1 transactions

  • if we find 2 zero-balance subgroups, one of size k and other n-k

    • instead of n-1 transactions with a same Clearing guy
    • make k-1 transactions within first group choosing a Clearing House guy, and n-k-1 transactions within second group choosing another Clearing House guy
    • only needs n-2 transactions

  • each zero-balance subgroup saves 1 transactions

  • find the maximum number of zero-balance subgroup!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int[] dp;
int n;
public int minTransfers(int[][] transactions) {
    Map<Integer,Integer> map=new HashMap<>();
    for (int[] arr : transactions) {
        map.put(arr[0],map.getOrDefault(arr[0],0)+arr[2]);
        map.put(arr[1],map.getOrDefault(arr[1],0)-arr[2]);
    }
    List<Integer> list=new ArrayList<>();
    for (Integer key : map.keySet()) {
        if(map.get(key)!=0){
            list.add(map.get(key));
        }
    }
    //debt: 3 means needing to give 3,
    // -3 means needing to receive 3
    int[] arr=list.stream().mapToInt(i->i).toArray();
    n=arr.length;
    dp=new int[1<<n]; //[1,1<<n -1]
    Arrays.fill(dp,-1);
    dp[0]=0;
    //注意：bit operation优先级低，一定要加括号
    return n-dfs(arr,(1<<n)-1);
}

private int dfs(int[] arr, int mask){
    //maximum number of sub groups that sum = 0
    //normally need n-1 transactions to settle a group
    //but if we find m subgroups of balance 0,
    //we only nned n-m transactions
    if(dp[mask]!=-1){
        return dp[mask];
    }
    int total=0;
    int max=0;
    for (int i = 0; i < n; i++) {
        int cur=1<<i;
        if((mask&cur)!=0){
            max=Math.max(max,dfs(arr,mask^cur));
            total+=arr[i];
        }
    }
    dp[mask]=max + (total==0 ? 1 : 0);
    return dp[mask];
}

2708. Maximum Strength of a Group

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int n;
int len;
long[][] dp;

public long maxStrength(int[] nums) {
    n=nums.length;
    len=(1<<n);
    dp=new long[len][2]; //positive, negative
    for (int i = 0; i < len; i++) {
        dp[i][0]=Integer.MIN_VALUE;
    }
    for (int i = 0; i < n; i++) {
        dp[(len-1)^(1<<i)][0]=nums[i];
        dp[(len-1)^(1<<i)][1]=nums[i];
    }
    return dfs(nums,0)[0];
}

private long[] dfs(int[] nums, int mask){
    if(dp[mask][0]!=Integer.MIN_VALUE){
        return dp[mask];
    }
    long min=Integer.MAX_VALUE;
    long max=Integer.MIN_VALUE;
    for (int i = 0; i < n; i++) {
        //mask[i]=0, nums[i] not chosen yet
        if((mask & (1<<i))==0){
            min=Math.min(min,nums[i]);
            max=Math.max(max,nums[i]);
            long[] sub=dfs(nums,mask^(1<<i));
            if(nums[i]>0){
                max=Math.max(max,sub[0]*nums[i]);
                min=Math.min(min,sub[1]*nums[i]);
            }else{
                max=Math.max(max,sub[1]*nums[i]);
                min=Math.min(min,sub[0]*nums[i]);
            }
            max=Math.max(max,sub[0]);
            min=Math.min(min,sub[1]);
        }
    }
    dp[mask][0]=max;
    dp[mask][1]=min;
    return dp[mask];
}