Han Zhu's Study Notes

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the  Hamming weight ). For example, the 32-bit integer ’11' has binary representation  00000000000000000000000000001011 , so the function should return 3. Thought process: Use Integer built-in method. Solution: 1 2 3 4 5 6 public class Solution { // you need to treat n as an unsigned value public int hammingWeight ( int n ) { return Integer . bitCount ( n ); } } Time complexity: O(n) where n is the number of bits of n.

Given an array containing  n  distinct numbers taken from  0, 1, 2, ..., n , find the one that is missing from the array. For example, Given  nums  =  [0, 1, 3]  return  2 . Note : Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity? Thought process: Use the XOR operation. a ^ a = 0. Since the numbers run from 0 to n, nums[i] ^ i = 0. If there's no number missing, nums[0] ^ 0 ^ nums[1] ^ 1 ^ ... ^ nums[n] ^ n = 0. Now that there's one number missing, the result of the above XOR calculation will give me the missing number. Solution: 1 2 3 4 5 6 7 8 9 10 11 class Solution { public int missingNumber ( int [] nums ) { int i = 0 ; int xor = 0 ; for (; i < nums . length ; i ++) { xor ^= i ^ nums [ i ]; } return xor ^ i ; } } Time complexity: O(n). S...

Given an array of size  n , find the majority element. The majority element is the element that appears  more than   ⌊ n/2 ⌋  times. You may assume that the array is non-empty and the majority element always exist in the array. Thought process: Brute force solution is trivial. Iterate through the array. Keep track of a majority element candidate and its count. Increment count if current number == majority and decrement count otherwise. Reset majority element and count if count == 0. At the end, if there's a majority element, count > 0. count is essentially count of majority elements - count of other numbers. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution { public int majorityElement ( int [] num ) { int majority = num [ 0 ]; int count = 1 ; for ( int i = 1 ; i < num . length ; i ++){ if ( count == 0 ) { count ++; ...

A character in UTF8 can be from  1 to 4 bytes  long, subjected to the following rules: For 1-byte character, the first bit is a 0, followed by its unicode code. For n-bytes character, the first n-bits are all one's, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10. This is how the UTF-8 encoding would work: Char. number range | UTF -8 octet sequence (hexadecimal) | (binary) --------------------+--------------------------------------------- 0000 0000 -0000 007 F | 0 xxxxxxx 0000 0080 -0000 07 FF | 110 xxxxx 10 xxxxxx 0000 0800 -0000 FFFF | 1110 xxxx 10 xxxxxx 10 xxxxxx 0001 0000 -0010 FFFF | 11110 xxx 10 xxxxxx 10 xxxxxx 10 xxxxxx Given an array of integers representing the data, return whether it is a valid utf-8 encoding. Note: The input is an array of integers. Only the  least significant 8 bits  of each integer is used to store the data. This means each integer repre...

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. Example: Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6. Note: Elements of the given array are in the range of  0  to  10^9 Length of the array will not exceed  10^4 . Thought process: A naive solution is to wrap a nested loop around the solution of "461. Hamming Distance" . This results in quadratic time complexity, which exceeds the time limit. A more efficient way to solve this is to iterate through the bits. Since max(nums) < 10^9, I know that the numbers won't take more than 32 bits. Say for one of t...

The  Hamming distance  between two integers is the number of positions at which the corresponding bits are different. Given two integers  x  and  y , calculate the Hamming distance. Note: 0 ≤  x ,  y  < 2 31 . Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ? ? The above arrows point to positions where the corresponding bits are different. Thought process: Count the number of 1 bit in x XOR y. Solution: 1 2 3 4 5 public class Solution { public int hammingDistance ( int x , int y ) { return Integer . bitCount ( x ^ y ); } } Time complexity: Say the larger number has n bits. The overall time complexity is O(n).

Given a set of  distinct  integers,  nums , return all possible subsets. Note:  The solution set must not contain duplicate subsets. For example, If  nums  =  [1,2,3] , a solution is: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] Thought process: Iterate through the list. For each number, iterate through the list again starting from that element. As I iterate, add elements to the current list. Delete the last added element after the recurrence. Solution 1: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class Solution { public List < List < Integer >> subsets ( int [] nums ) { List < List < Integer >> subsets = new ArrayList <>(); List < Integer > subset = new ArrayList <>(); subsets ( nums , 0 , subset , subsets ); return subsets ; } private void subsets ( int [] nums , int start , ...

Reverse bits of a given 32 bits unsigned integer. For example, given input 43261596 (represented in binary as  00000010100101000001111010011100 ), return 964176192 (represented in binary as  00111001011110000010100101000000 ). Follow up : If this function is called many times, how would you optimize it? Related problem:  Reverse Integer Thought process: Right shift the number until it's 0. For every bit, if it's 1, add n & 1 to the reversed number, and right-shift n. Because input number is a 32 bits unsigned integer, and Java int is 32 bits signed, I should not left-shift reversed if it's the last bit. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 public class Solution { // you need treat n as an unsigned value public int reverseBits ( int n ) { int reversed = 0 ; for ( int i = 0 ; i < 32 ; i ++) { reversed += n & 1 ; n >>>= 1 ; ...

Given a non negative integer number  num . For every numbers  i  in the range  0 ≤ i ≤ num  calculate the number of 1's in their binary representation and return them as an array. Example: For  num = 5  you should return  [0,1,1,2,1,2] . Follow up: It is very easy to come up with a solution with run time  O(n*sizeof(integer)) . But can you do it in linear time  O(n)  /possibly in a single pass? Space complexity should be  O(n) . Can you do it like a boss? Do it without using any builtin function like  __builtin_popcount  in c++ or in any other language. Hint: You should make use of what you have produced already. Divide the numbers in ranges like [2-3], [4-7], [8-15] and so on. And try to generate new range from previous. Or does the odd/even status of the number help you in calculating the number of 1s? Thought process: GCC has a built-in function called "__builtin_popcount", which can ret...

Given an integer, write a function to determine if it is a power of two. Thought process: If the number is not positive, return false directly. Divide the number by 2 until it becomes an odd number. If it's not 1, return false. Otherwise, return true. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: bool isPowerOfTwo( int n) { if (n <= 0 ) { return false ; } while ( ! (n & 1 )) { n /= 2 ; } return n == 1 ; } }; Time complexity: O(logn).

Given an array of integers, every element appears  twice  except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Thought process: Iterate through the array. Maintain a set of integers seen so far. If a number is already in the set, erase it from the set. In the end the set will have one element remaining, which is the single number. Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution { public: int singleNumber(vector < int >& nums) { unordered_set < int > set; for ( int num : nums) { if ( ! set.insert(num).second) { set.erase(num); } } return * set.begin(); } }; Time complexity: O(n). Space complexity: O(n). Follow-up: This problem can be solved without using extra space using the XOR operation. A XOR A = 0. By XORing ...