# Posts published in “Bit”

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)

Problem:

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:

Example 2:

Example 3:

Example 4:

Idea:

Bit operation

Solution

C++