# Posts published in “Bit”

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:

Example 2:

Note:

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

Solution 1: Brute Force

C++

Java

Python2

Python2

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:

Note:

1. The array is only modifiable by the update function.
2. 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++

Problem:

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

Note:

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

Example 1:

Example 2:

Idea:

Bit

Solution:

C++

Problem:

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:

Note:

1. Elements of the given array are in the range of 0 to 10^9
2. Length of the array will not exceed 10^4.

Idea:

1. Brute force, compute HammingDistance for all pairs. O(n^2) TLE
2. Count how many ones on i-th bit, assuming k. Distance += k * (n – k). O(n)

Solution:

C++ / O(n)

Problem:

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.

Ideas:

Solution 1:

Hash table O(n) / O(n)

Solution 2:

BST O(nlogk) / O(n)

Solution 3:

Randomization O(n) / O(1)

Solution 4:

Bit voting O(n) / O(1)

Solution 5:

Moore Voting O(n) / O(1)

Solution 6:

Full sorting O(nlogn) / O(1)

Solution 7:

Partial sorting O(n) / O(1)

Solution 8:

Divide and conquer O(nlogn) / O(logn)

Divide and conquer O(nlogn) / O(logn)

Mission News Theme by Compete Themes.