201. Bitwise AND of Numbers Range

Difficulty: Medium

Frequency: N/A

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        int shift = 0;
        while (m != n) {
            shift++;
            m = m >> 1;
            n = n >> 1;
        }
        return m << shift;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:
Advertisements

260. Single Number III

Difficulty: Medium

Frequency: N/A

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

  1. The order of the result is not important. So in the above example, [5, 3] is also correct.
  2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int two_num = 0;
        for (int num : nums) two_num = two_num ^ num;
        int set_bit = 0;
        for (set_bit = 0; set_bit < 32; set_bit++) {
            if ((two_num >> set_bit & 1) == 1) break;
        }
        int result = 0;
        for (int num : nums) {
            if ((num >> set_bit & 1) == 1) result = result ^ num;
        }
        vector<int> results = {result, result ^ two_num};
        return results;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

318. Maximum Product of Word Lengths

Difficulty: Medium

Frequency: N/A

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.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]
Return 16
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]
Return 4
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]
Return 0
No such pair of words.


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int maxProduct(vector<string>& words) {
        vector<int> masks(words.size(), 0);
        int result = 0;
        for (int i = 0; i < words.size(); i++) {
            for (char c : words[i]) {
                masks[i] = masks[i] | 1 << (c - 'a');
            }
            for (int j = 0; j < i; j++) {
                if (masks[j] & masks[i]) continue;
                result = max(result, int(words[i].size() * words[j].size()));
            }
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

190. Reverse Bits

Difficulty: Easy

Frequency: N/A

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

Related problem: Reverse Integer


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) + (n >> i & 1);
        }
        return result;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

231. Power of Two

Difficulty: Easy

Frequency: N/A

Given an integer, write a function to determine if it is a power of two.

My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return (n > 0 && !(n & (n - 1)));
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

137. Single Number II

Difficulty: Medium

Frequency: N/A

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

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?


My solution:
Data structure:
Steps:
Complexity:
Runtime:
Space:
Test cases:
Corner cases:
Code:
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            int ta = (a & ~b & ~num) | (~a & b & num);
            b = (~a & b & ~num) | (~a & ~b & num);
            a = ta;
        }
        return a | b;
    }
};

Another solution:
Data structure:
steps:
Complexity:
Runtime:
Space:
Code:

Things to learn:

Bit Manipulation

OR

  • OR is used for setting a bit regardless of the other bit.
  • When you want to set a bit to 1, just ‘OR’ the bit with 1
  • If x denotes a bit(0 or 1), then the following hold true.
  • x | 0 = x (i.e. OR ing with 0 retains the original bit.)
  • x | 1 = 1 (i.e. OR ing with 1 sets the bit to 1.)

Examples

  • Set the last digit to 1
    x | 1
  • Set the number to its closest even number (i.e. set the last digit to 0)
    (x | 1) - 1
  • Set the k-th digit to 1, e.g. 0b101001 -> 0b101101, k=3
    x | (1 << (k-1))
  • Set the last k digits to 1, e.g. 0b101001 -> 0b101111, k=3
    x | (1 << k - 1)
  • Flip the last continuous 0’s to 1’s, e.g. 0b10110000 -> 0b10111111
    x | (x-1)
  • Flip the first 0 to 1 (starting from right), e.g. 0b10101011 -> 0b10101111
    x | (x+1)

 

AND

  • AND can be used for clearing a bit.
  • When you want to ‘clear’ a bit, just ‘AND’ it with 0.
  • AND can be used for checking whether a bit is set.
  • To check whether a bit is set, just ‘AND’ it with 1, it will return whether that bit was set.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x & 0 = 0 (i.e. AND ing with 0 clears the bit to 0)
  • x & 1 = x (i.e. AND ing with 1 retains the original bit)

Examples

  • What’s the k-th digit of x?
    (x >> (k-1)) & 1
  • Is a number odd? (I.e., Is the last digit 1?)
    (x & 1) == 1
  • What’s the last k digits of x?
    x & (1 << k - 1)
  • What’s the last 3 digits of x?
    x & 0x111
  • Set the k-th digit to 0, e.g. 0x101101 -> 0x101001, k=3
    x & ~(1 << (k-1))
  • Is a number pow of 2?
    (x != 0) && (x & (x-1) ==0), i.e. x && !(x & (x - 1))
  • Flip the last continuous 1’s to 0’s, e.g. 0b10101111 -> 0b10100000
    x & (x+1)
  • N & 0xFF = least significant byte of integer or the last 8 bits of integer.

 

XOR

  • for flipping selective bits, XOR is chosen.
  • for flipping a bit, XOR it with 1, it will get reversed.
  • If x denotes a bit(0 or 1), then the following hold true.
  • x ^ 1 = ~x (XOR ing with 1 flips the bits)

Examples

  • Flip k-th digit
    x ^ (1 << (k-1))
  • Flip last k digits
    x ^ (1 << k - 1)
  • Get the last continuous 1’s, e.g. 0b10101111 -> 0b1111
    (x ^ (x+1)) >> 1
  • Remove the left of the first 1 from the right, e.g. 0b10101000 -> 0b1000
    (x ^ (x-1)) >> 1 + 1   or   x ^ (x-1) & x
  • Swap two numbers
    One way to swap two numbers is to use + and – (two inverse operations):
    a = a + b;  b = a - b;  a = a - b;
    And we can use xor and since its inverse operation is itself:
    a = a ^ b;  b = a ^ b;  a = a ^ b;

 

NOT

  • The bitwise complement operator, ~, flips every bit in a number.

Examples

  •  ~N + 1 = -N

 

SHIFT

  • Left Shift
    • symbol is ‘<<‘
    • x << y means x shifted y bits to the left.
    • If you run out of space, bits drop off from the left.
  • Right Shift
    • symbol is ‘>>’
    • x >> y means x shifted y bits to the right.
    • If you run out of space, bits drop off from the right.

Examples

  • Remove the last digit
    x >> 1
  • Add a 0 to the end of a number
    x << 1
  • Add an 1 to the end of a number
    x << 1 + 1
  • N << 1 = N*2
  • N << 2 = N*pow(2,2)
  • N << k = N*(pow(2,k))
  • N >> 1 = floor(N/2)
  • N >> 2 = floor(N/pow(2,2))
  • N >> k = floor(N/pow(2,k))