花花酱 LeetCode 289. Game of Life

By zxi on June 27, 2018

Problem

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies, as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population..
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

Input: 
[
  [0,1,0],
  [0,0,1],
  [1,1,1],
  [0,0,0]
]
Output: 
[
  [0,0,0],
  [1,0,1],
  [0,1,1],
  [0,1,0]
]

Follow up:

Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

Solution: Simulation

Time complexity: O(mn)

Space complexity: O(1)

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

void gameOfLife(vector<vector<int>>& board) {

int m = board.size();

int n = m ? board[0].size() : 0;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

int lives = 0;

// Scan the 3x3 region including (j, i).

for (int y = max(0, i - 1); y < min(m, i + 2); ++y)

for (int x = max(0, j - 1); x < min(n, j + 2); ++x)

lives += board[y][x] & 1;

if (lives == 3 || lives - board[i][j] == 3) board[i][j] |= 0b10;

}

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j)

board[i][j] >>= 1;

}

};

花花酱 LeetCode 810. Chalkboard XOR Game

By zxi on May 2, 2018

Problem

We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Notes:

1 <= N <= 1000.
0 <= nums[i] <= 2^16.

Solution: Math

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

bool xorGame(vector<int>& nums) {

if (nums.size() % 2 == 0) return true;

int x = 0;

for (int num : nums) x ^= num;

return x == 0;

}

};

花花酱 LeetCode 461. Hamming Distance

By zxi on March 19, 2018

Problem

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³¹.

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.

Solution: Bit Operation

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 6 ms

class Solution {

public:

int hammingDistance(int x, int y) {

int ans = 0;

int t = x^y;

while (t) {

ans += t & 1;

t >>=1;

}

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int hammingDistance(int x, int y) {

return __builtin_popcount(x ^ y);

}

};

Problem:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution 1:

Time complexity: O(11*59*n)

C++

// Author: Huahua

// Running time: 2 ms (beats 100%)

class Solution {

public:

vector<string> readBinaryWatch(int num) {

vector<string> ans;

for (int i = 0; i <= num; ++i)

for (int h : nums(i, 12))

for (int m : nums(num - i, 60))

ans.push_back(to_string(h) + (m < 10 ? ":0" : ":") + to_string(m));

return ans;

}

private:

// Return numbers in [0,r) that has b 1s in their binary format.

vector<int> nums(int b, int r) {

vector<int> ans;

for (int n = 0; n < r; ++n)

if (__builtin_popcount(n) == b) ans.push_back(n);

return ans;

}

};

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

By zxi on January 17, 2018

题目大意：求给定范围内，数的二进制形式中1的个数为素数个的数字的个数。

Given two integers L and R, find the count of numbers in the range [L, R] (inclusive) having a prime number of set bits in their binary representation.

(Recall that the number of set bits an integer has is the number of 1s present when written in binary. For example, 21 written in binary is 10101 which has 3 set bits. Also, 1 is not a prime.)

Example 1:

Input: L = 6, R = 10

Output: 4

Explanation:

6 -> 110 (2 set bits, 2 is prime)

7 -> 111 (3 set bits, 3 is prime)

9 -> 1001 (2 set bits , 2 is prime)

10->1010 (2 set bits , 2 is prime)

Example 2:

Input: L = 10, R = 15

Output: 5

Explanation:

10 -> 1010 (2 set bits, 2 is prime)

11 -> 1011 (3 set bits, 3 is prime)

12 -> 1100 (2 set bits, 2 is prime)

13 -> 1101 (3 set bits, 3 is prime)

14 -> 1110 (3 set bits, 3 is prime)

15 -> 1111 (4 set bits, 4 is not prime)

Note:

L, R will be integers L <= R in the range [1, 10^6].
R - L will be at most 10000.

Solution 1: Brute Force

C++

// Author: Huahua

// Running time: 22 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private:

bool isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

int bits(int n) {

int s = 0;

while (n) {

s += n & 1;

n >>= 1;

}

return s;

}

};

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 30 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

unordered_set<int> primes{2, 3, 5, 7, 11, 13, 17, 19};

for (int n = L; n <= R; ++n)

if (primes.count(__builtin_popcountll(n))) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 9 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

int ans = 0;

vector<int> p(20, 0);

p[2] = p[3] = p[5] = p[7] = p[11] = p[13] = p[17] = p[19] = 1;

for (int n = L; n <= R; ++n)

if (p[__builtin_popcountll(n)]) ++ans;

return ans;

}

};

// Author: Huahua

// Running time: 8 ms

class Solution {

public:

int countPrimeSetBits(int L, int R) {

constexpr int magic = 665772;

int ans = 0;

for (int n = L; n <= R; ++n)

if (magic & (1 << __builtin_popcountll(n))) ++ans;

return ans;

}

};

Java

// Author: Huahua

// Running time: 39 ms

class Solution {

public int countPrimeSetBits(int L, int R) {

int ans = 0;

for (int n = L; n <= R; ++n)

if (isPrime(bits(n))) ++ans;

return ans;

}

private boolean isPrime(int n) {

if (n <= 1) return false;

if (n == 2) return true;

for (int i = 2; i <= (int)Math.sqrt(n); ++i)

if (n % i == 0) return false;

return true;

}

private int bits(int n) {

int s = 0;

while (n != 0) {

s += n & 1;

n >>= 1;

}

return s;

}

Python2

"""

Author: Huahua

Running time: 1618 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def isPrime(n):

if n <= 1: return False

if n == 2: return True

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0: return False

return True

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

ans = 0

for n in range(L, R + 1):

if isPrime(bits(n)): ans += 1

return ans

Python2

"""

Author: Huahua

Running time: 1163 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

s += n & 1

n >>= 1

return s

primes = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31])

ans = 0

for n in range(L, R + 1):

if bits(n) in primes: ans += 1

return ans

"""

Author: Huahua

Running time: 667 ms

"""

class Solution(object):

def countPrimeSetBits(self, L, R):

def bits(n):

s = 0

while n != 0:

n &= n - 1;

s += 1

return s

ans = 0

while L <= R:

if (665772 >> bits(L)) & 1 > 0: ans += 1

L += 1

return ans

Posts tagged as “bit”

花花酱 LeetCode 289. Game of Life

Problem

Solution: Simulation

花花酱 LeetCode 810. Chalkboard XOR Game

Problem

Solution: Math

花花酱 LeetCode 461. Hamming Distance

Problem

Solution: Bit Operation

Related Problems

花花酱 LeetCode 401. Binary Watch

Problem:

Solution 1:

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation

Posts tagged as “bit”

花花酱 LeetCode 289. Game of Life

Problem

Solution: Simulation

花花酱 LeetCode 810. Chalkboard XOR Game

Problem

Solution: Math

花花酱 LeetCode 461. Hamming Distance

Problem

Solution: Bit Operation

Related Problems

花花酱 LeetCode 401. Binary Watch

Problem:

<img src="https://upload.wikimedia.org/wikipedia/commons/8/8b/Binary_clock_samui_moon.jpg" height="300"/>

Solution 1:

花花酱 LeetCode 762. Prime Number of Set Bits in Binary Representation