Posts published in “Bit”

花花酱 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

花花酱 307. Range Sum Query – Mutable

By zxi on January 3, 2018

题目大意：给你一个数组，让你求一个范围之内所有元素的和，数组元素可以更改。

Problem:

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.

Example:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

Note:

The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.

Idea:

Fenwick Tree

Solution:

C++

Time complexity:

init O(nlogn)

query: O(logn)

update: O(logn)

C++

// Author: Huahua

// Running time: 83 ms

class FenwickTree {

public:

FenwickTree(int n): sums_(n + 1, 0) {}

void update(int i, int delta) {

while (i < sums_.size()) {

sums_[i] += delta;

i += lowbit(i);

}

int query(int i) const {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= lowbit(i);

}

return sum;

}

private:

static inline int lowbit(int x) { return x & (-x); }

vector<int> sums_;

};

class NumArray {

public:

NumArray(vector<int> nums): nums_(std::move(nums)), tree_(nums_.size()) {

for (int i = 0; i < nums_.size(); ++i)

tree_.update(i + 1, nums_[i]);

}

void update(int i, int val) {

tree_.update(i + 1, val - nums_[i]);

nums_[i] = val;

}

int sumRange(int i, int j) {

return tree_.query(j + 1) - tree_.query(i);

}

private:

vector<int> nums_;

FenwickTree tree_;

};

Java

// Author: Huahua

// Running time: 130 ms

class NumArray {

FenwickTree tree_;

int[] nums_;

public NumArray(int[] nums) {

nums_ = nums;

tree_ = new FenwickTree(nums.length);

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

tree_.update(i + 1, nums[i]);

}

public void update(int i, int val) {

tree_.update(i + 1, val - nums_[i]);

nums_[i] = val;

}

public int sumRange(int i, int j) {

return tree_.query(j + 1) - tree_.query(i);

}

class FenwickTree {

int sums_[];

public FenwickTree(int n) {

sums_ = new int[n + 1];

}

public void update(int i, int delta) {

while (i < sums_.length) {

sums_[i] += delta;

i += i & -i;

}

public int query(int i) {

int sum = 0;

while (i > 0) {

sum += sums_[i];

i -= i & -i;

}

return sum;

}

Python3

"""

Author: Huahua

Running time: 192 ms (< 90.00%)

"""

class FenwickTree:

def __init__(self, n):

self._sums = [0 for _ in range(n + 1)]

def update(self, i, delta):

while i < len(self._sums):

self._sums[i] += delta

i += i & -i

def query(self, i):

s = 0

while i > 0:

s += self._sums[i]

i -= i & -i

return s

class NumArray:

def __init__(self, nums):

self._nums = nums

self._tree = FenwickTree(len(nums))

for i in range(len(nums)):

self._tree.update(i + 1, nums[i])

def update(self, i, val):

self._tree.update(i + 1, val - self._nums[i])

self._nums[i] = val

def sumRange(self, i, j):

return self._tree.query(j + 1) - self._tree.query(i)

Solution 2: Segment Tree

C++

// Author: Huahua, running time: 24 ms

class SegmentTreeNode {

public:

SegmentTreeNode(int start, int end, int sum,

SegmentTreeNode* left = nullptr,

SegmentTreeNode* right = nullptr):

start(start),

end(end),

sum(sum),

left(left),

right(right){}

SegmentTreeNode(const SegmentTreeNode&) = delete;

SegmentTreeNode& operator=(const SegmentTreeNode&) = delete;

~SegmentTreeNode() {

delete left;

delete right;

left = right = nullptr;

}

int start;

int end;

int sum;

SegmentTreeNode* left;

SegmentTreeNode* right;

};

class NumArray {

public:

NumArray(vector<int> nums) {

nums_.swap(nums);

if (!nums_.empty())

root_.reset(buildTree(0, nums_.size() - 1));

}

void update(int i, int val) {

updateTree(root_.get(), i, val);

}

int sumRange(int i, int j) {

return sumRange(root_.get(), i, j);

}

private:

vector<int> nums_;

std::unique_ptr<SegmentTreeNode> root_;

SegmentTreeNode* buildTree(int start, int end) {

if (start == end) {

return new SegmentTreeNode(start, end, nums_[start]);

}

int mid = start + (end - start) / 2;

auto left = buildTree(start, mid);

auto right = buildTree(mid + 1, end);

auto node = new SegmentTreeNode(start, end, left->sum + right->sum, left, right);

return node;

}

void updateTree(SegmentTreeNode* root, int i, int val) {

if (root->start == i && root->end == i) {

root->sum = val;

return;

}

int mid = root->start + (root->end - root->start) / 2;

if (i <= mid) {

updateTree(root->left, i, val);

} else {

updateTree(root->right, i, val);

}

root->sum = root->left->sum + root->right->sum;

}

int sumRange(SegmentTreeNode* root, int i, int j) {

if (i == root->start && j == root->end) {

return root->sum;

}

int mid = root->start + (root->end - root->start) / 2;

if (j <= mid) {

return sumRange(root->left, i, j);

} else if (i > mid) {

return sumRange(root->right, i, j);

} else {

return sumRange(root->left, i, mid) + sumRange(root->right, mid + 1, j);

}

};

花花酱 LeetCode 476. Number Complement

By zxi on December 29, 2017

题目大意：给你一个正整数，输出和它互补的数（翻转所有的bits）。

Problem:

Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.

Note:

The given integer is guaranteed to fit within the range of a 32-bit signed integer.
You could assume no leading zero bit in the integer’s binary representation.

Example 1:

Input: 5

Output: 2

Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: 1

Output: 0

Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

Idea:

Bit

Solution:

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int findComplement(int num) {

int mask = ~0;

while (num & mask) mask <<= 1;

return ~num ^ mask;

}

};

Posts published in “Bit”

花花酱 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

花花酱 307. Range Sum Query – Mutable

C++

Java

Python3

Solution 2: Segment Tree

C++

花花酱 LeetCode 476. Number Complement

Posts published in “Bit”

花花酱 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

花花酱 307. Range Sum Query – Mutable

C++

Java

Python3

Solution 2: Segment Tree

C++

花花酱 LeetCode 476. Number Complement