Bit Manipulation (BP)

461 Hamming Distance

(1) let z = x ^ y (2) count how many 1s in z's binary representation in a loop. 169 Majority Element The idea is to iterate each bit of all the numbers and try to get the statistics of each bit. If a given bit has more ones than zeros then set the result bit to 1, otherwise set it to zero. 187 Repeated DNA Sequences     Use a hash map to count each 10 character string frequency. In the second loop, loop each map element to check f its frequency is > 1, put it in the result array. Return the result array in the end. No need to calculate the hash key as binary number using bit manipulation. 231 Power of Two      return n <= 0 ? false : (n ^ (n - 1)) == 0; 342 Power of Four     Add one extra check based on 231:  (n & 0x55555555) != 0 191 Number of 1 Bits     Loop and count each 1 bit (n & (0x1 << 1)( in the 32-bit binary representation  476 Number Complement    I basically check every bit of number by XOR'ing it with appropriate power of 2 which leads to its invertion. For example: Entered: 4=>100; 100 ^ 001 = 101; 101 ^ 010 = 111; 111 ^ 100 = 011; Out: 011=>3;   371 Sum of Two Integers   the addition op can be split into two parts, the carry part and the non-carry part. the carry part can be calcuated by bit and (&) followed by left shift one bit. While the non-carry part can be calculated by bit xor (^). Do the following in a loop: tmp = (a & b) << 1 (the carray part), b = a ^ b (non-carry part), a = tmp. Until there is no carry any more, then return the non carry part b.     136 Single Number      We could use hash map to solve this in O(N) time and O(N) space. But an even better way is to use bit manipulation. Since we know there is only one number appears once, all the others appears twice. If we xor all the numbers. The result will be the number just appeared once. One sentence summary:  xor all the numbers in a loop. (vector array version xor)   137 Single Number II     Similar to 260 Single Number III. Still check each bit of every number. But this time we want to count bit ones for  each bit say n. If n % 3 ! = 0, then set that result bit to 1. Return the res in  the end.   389 Find the Difference   Exactly the same idea with 136. (string version xor)     268 Missing Number  Also similar to 136, 389. Just a little bit effort to figure out that we need to also xor the array index. Define res = 0. and Then for loop each number in the array from 0 to n - 1. do  res ^= i ^ nums[i]. Then after the loop, res ^= n; return res.         693 Binary Number with Alternating Bits       Smart solution. Using the fact that if n is a alternating number then n + (n >> 1) is all 1s, and n + (n >> 1) + 1 should be power of 2. And since we know, any number that is a power of two, have an attribute which is n & (n - 1) is 0. We just need to check that.       762  Prime Number of Set Bits in Binary Representation     Loop each number from L to R inclusively. Count how many 1s are there in their  binary representation. Check whether the number is prime. For prime check we can hard code all the primes into a hash set and use count(n) to check whether n is a  primer number.         190 Reverse Bits lg(N) in place alrogithm: n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1); // swap odd even bits n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2); // swap odd even 2-bit n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4); // swap odd even 4-bit n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8); // swap odd even 8-bit n = ((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16); // swap odd even 16-bit return n;     78 Subsets  (1) Calculate the total number of subsets pow2n = 2^n. And initialize the result  vector<vector<int> > res to have pow2n empty() vector<int>() (2) for loop each i from 0 to pow2n - 1, and (3) inside the inner loop (j from 0 - (n -1)) check each bit of i, if it is one then add that number to the current set res[i], otherwise skip it. (4) return res in the end. O(N*2^N) time and O(1) extra space. Second Time =================================================================       Calculate bit by bit  477 Total Hamming Distance    This is one kind of problems, they are loop each bit of a group of numbers do some  calculation to reduce time complexity (usually from O(N^2) to O(N) This problem, we know that if we loop each bit of the numbers, and count 1s and 0s, the  hamming distance for that particular bit is zeros * ones. If we sum up all the zeros *  ones for every bit. We get all the total hamming distance.   Note: the calculation for each bit must be independent with each other to be eligible to use this algorithm.     DP / DFS    756 Pyramid Transition Matrix  The idea is to use a string to set hash map to save all the possible transition map. And then use a DFS helper to construct the possible pyramid.   bool DFS(string cur, string above, unordered_map<string, unordered_set<char> >& mp)   (1) Base case: if cur.size() == 2 && above.size() == 1, return true (2) Recursion formula: if (cur.size() == above.size() + 1), recursively call DFS(above, "", mp), since that means the current level is successfully constructed. (3) Otherwise when cur.size() > above.size() + 1, in the middle of building. get the base string: base = cur.substr(above.size(), 2); If base exist in the map then for loop each possible char that could be used to build the next level to see whether if any could be used to build the above level successfully. If any, return  true.  (4) If no early exit, in the end, return false meaning couldn't build the pyramid. O(2^N) time       318 Maximum Product of Word Lengths     Two ways but the same idea (1) hash set. Loop each word i from 0 to n - 2. And inner loop another word j from   i to n - 1. Put all the chars in word[i] into a set. And check whether any char in word[j] occurs in the set. If so continue next word[j + 1] otherwise if none  of the char in word[j] occurs in word[i] set. Update the res with word[i].size() * word[j].size() if it is greater than the current res. (2) Instead of using hash set. We could use a bit mask integer to mimic hash set. for each char c in the word[i], set the (c - 'a') th bit in the mask.  mask[i] |= (1 << (c - 'a')); Instead of check hashSet.find(c) != hashSet.end() we check whether (mask[i] & mask[j] != 0) meaning having overlapping characters. Both are O(26*N^2) time and O(26*N) space.     393 UTF-8 Validation  Define a count variable to denote how many remaining bytes still left for the current valid UTF-8 character and initialize it to zero  (1) For loop each char in the data and do the following (2) When count == 0. Do the following check. if high 3 bits are 0b110, set count to 1.  Else if high 4 bits are 0b1110, set count to 2. Else if high 5 bits are 0b11110, set  count to 3. Else if MSB is not 0, return false (invalid). Implicitly, we known MSB is   0, we just loop next byte in the data. (3) If count != 0, meaning it is the 2/3/4 byte in the character. Check whether the byte begin with 0b10, if not return false. Otherwise, count--. (4) In the end, if count == 0, then it is valid, otherwise, invalid.     201 Bitwise AND of Numbers Range   every time get rid of one bit, O(lg(N - M)) time and O(1) space int rangeBitwiseAnd(int m, int n) { while (m < n) n &= n - 1; return n; }      338 Counting Bits    // i bin '1' i&(i-1) // 0000 0 // ----------------------- // 0001 1 0000 // ----------------------- // 0010 1 0000 // 0011 2 0010 // ----------------------- // 0100 1 0000 // 0101 2 0100 // 0110 2 0100 // 0111 3 0110 // ----------------------- // 1000 1 0000 // 1001 2 1000 // 1010 2 1000 // 1011 3 1010 // 1100 2 1000 // 1101 3 1100 // 1110 3 1100 // 1111 4 1110 // 我们可以发现每个i值都是i&(i-1)对应的值加1，这样我们就可以写出代码如下 vector<int> countBits(int num) { vector<int> res(num + 1, 0); for (int i = 1; i <= num; i++) res[i] = res[i & (i - 1)] + 1; return res; }   405 Convert a Number to Hexadecimal  Define HEX = "0123456789abcdef"; while (num && count++ < 8) {   res = HEX[num & 0xf] + res; num >>= 4; } return res;     421 Maximum XOR of Two Numbers in an Array Loop from MSB to LSB. And save the prefix of all the numbers in a set. And assume the current bit in the final result max can be set to 1. Then try to find whether max ^ pre is in the prefix set. If so update max = max ^ pre. Keep doing this for every bit from MSB to LSB. In the end return max.     397 Integer Replacement   Only when there are more trailing zeros in n+ 1 than n - 1, we want to increase n,  otherwise we decrease n (note n == 3 is a special case) 401 Binary Watch   Idea: For loop each hour and minutes combination to count how many bits are set in the hour and minutes. If the number is equal to the given number of LED lights, then push it into the result string. In the end return the result string.   // the description says h in [0 - 11], and m in [0 - 59] vector<string> readBinaryWatch(int num) { vector<string> res; for (int h = 0; h < 12; h++) for (int m = 0; m < 60; m++) if (bitset<10>(h << 6 | m).count() == num) res.emplace_back(to_string(h) + ":" + (m < 10 ? "0" : "") + to_string(m)); return res;     260 Single Number III   Extension to 136 Single Number. (1) get the aXORb result in the first loop by XORing all the numbers together. (2) get the last bit 1 by aXORb ^ (~(aXORb - 1)) (3) Loop all the numbers again, if the bit at last bit calculated in step two is 1,  XOR it with a, otherwise XOR it with b (so that we can construct the number a ending with 1 by xoring all the numbers ending with 1 including a itself. (4) After the loop in step 3, we get the two single numbers a, b.   784 Letter Case Permutation     Backtrack DFS   Time complexity O(N*2^I) I: # of letters Space complexity O(n) + O(N*2^I) stack + sols?   def dfs(S, i)   if i == len(S) ans.append(S) return dfs(S, i + 1) if S[i] is letter :   toggle S[i] # S[i] ^= (1 << 5) dfs(S, i + 1) toggle back S[i] # S[i] ^= (1 << 5)   ref: http://zxi.mytechroad.com/blog/searching/leetcode-784-letter-case-permutation/   89 Gray Code      BC: Binary Code, GC: Gray Code. BC to GC formula : num ^ (num >> 1) GC to BC formula : num ^ (num >> 1) ^ (num >> 2) ...^(num >> (len(num) - 1))