**X. O(32n) - bit counting**

LeetCode 169 - Majority Element

**LeetCode 229 - Majority Number II**

- Boyer-Moore Majority Vote (not bit count)

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array. Find it.

**LeetCode 137 - Single Number II**

Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

LeetCode 477 - Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

**LintCode 196 - Find the Missing Number I**

Given an array contains N numbers of 0 .. N, find which number doesn't exist in the array.

for (int i = 0; i < nums.length; i++) {

result ^= i;

result ^= nums[i];

}

result ^= nums.length;

**X. Use bit to store info**

LeetCode 187 - Repeated DNA Sequences

LeetCode 318 - Maximum Product of Word Lengths

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

private int getMask(String s){

int mask = 0;

for(char c: s.toCharArray()){

mask |= 1 << (c - 'a');

}

return mask;

}

**X. Bit String**

**LeetCode 320 - Generalized Abbreviation**

Write a function to generate the generalized abbreviations of a word.

Example:

Given "word"

Return the following list (order does not matter):

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

X. Bit String

There exists a one to one mapping between abbreviation words and 2 based numbers.

Taking

`w2d`

for `word`

as an example.```
w2d--->0110
0110-->w11d-->w2d
```

So to get all the abbreviations for a word, first generate all the 2 based numbers within [0, 2^n -1] then maps each 2 based number to proper abbreviation string.

X. Bit String

`public List` generateAbbreviations(String word) {
List result = new ArrayList();
int maxLen = 1<for

X. DFS

`public List` generateAbbreviations(String word) {
List res = new ArrayList<>();
DFS(res, new StringBuilder(), word.toCharArray(), 0, 0);
return res;
}
public void DFS(List res, StringBuilder sb, char[] c, int i, int num) {
int len = sb.length();
if(i == c.length) {
if(num != 0) sb.append(num);
res.add(sb.toString());
} else {
DFS(res, sb, c, i + 1, num + 1); // abbr c[i]
if(num != 0) sb.append(num); // not abbr c[i]
DFS(res, sb.append(c[i]), c, i + 1, 0);
}
sb.setLength(len);
}

**X. Bit Trie**

LeetCode 421 - Maximum XOR of Two Numbers in an Array

Given a list of numbers, a[0], a[1], a[2], … , a[N-1], where 0 <= a[i] < 2^32. Find the maximum result of a[i] XOR a[j].