Application of Bit

Missing Number & Single Number & Find the Difference

public int missingNumber(int[] nums) {
    int res = nums.length;
    for (int i = 0; i < nums.length; i++) {
        res = res ^ i ^ nums[i];
    }
    return res;
}
public int singleNumber(int[] nums) {
    int res = 0;
    for (int i : nums) {
        res ^= i;
    }
    return res;
}

Majority Element

public int majorityElement(int[] nums) {
    int res = 0, [] bits = new int[32];

    for (int i = 0; i < 32; i++) {
        for (int num : nums) {
            bits[i] += ((num >> i) & 1);
        }
    }

    for (int i = 0, mask = 1; i < 32; i++, mask <<= 1) {
        if (bits[i] <= nums.length / 2) continue;
        res |= mask;
    }
    return res;
}

Integer Replacement

Repeated DNA Sequences

Maximum Product of Word Lengths

Binary Watch

/* Bit Wise*/
 public List<String> readBinaryWatch(int num) {
    List<String> res = new ArrayList<>();
    for (int i = 0; i < 12; i++) {
        for (int j = 0; j < 60; j++) {
            if (Integer.bitCount(i) + Integer.bitCount(j) == num) 
                res.add(String.format("%d:%02d", i, j));
        }
    }
    return res;
}
/* DFS */
public List<String> readBinaryWatch(int num) {
    List<String> ans = new LinkedList<>();
    dfs(ans, num, 0, new int[2]);
    return ans;
}
private void dfs(List<String> ans, int k, int i, int[] hhmm) {
    if (i == 10 || k <= 0) {
        if (k == 0 && hhmm[0] < 12 && hhmm[1] < 60) 
            ans.add(String.format("%d:%02d", hhmm[0], hhmm[1]));
        return;
    }
    int idx = i < 4 ? 0 : 1;
    int val = 1 << (i < 4 ? i : i - 4);
    hhmm[idx] += val;
    dfs(ans, k - 1, i + 1, hhmm);
    hhmm[idx] -= val;
    dfs(ans, k, i + 1, hhmm);
}

Subsets & Generalized Abbreviation

public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    //Arrays.sort(nums);
    int total = (int)Math.pow(2, nums.length);
    for (int i = 0; i < total; i++) {
        List<Integer> temp = new ArrayList<>();
        for (int j = 0; j < nums.length; j++) {
            if ((i & (1 << j)) != 0) {
                temp.add(nums[j]);
            }
        }
        res.add(new ArrayList<>(temp));
    }
    return res;
}

public List<String> generateAbbreviations(String word) {
    List<String> ret = new ArrayList<>();
    int n = word.length();
    for(int mask = 0;mask < (1 << n);mask++) {
        int count = 0;
        StringBuffer sb = new StringBuffer();
        for(int i = 0;i <= n;i++) {
            if(((1 << i) & mask) > 0) {
                count++;
            } else {
                if(count != 0) {
                    sb.append(count);
                    count = 0;
                }
                if(i < n) sb.append(word.charAt(i));
            }
        }
        ret.add(sb.toString());
    }
    return ret;
}

Minimum Unique Word Abbreviation