Posts tagged as “bit”

花花酱 LeetCode 1356. Sort Integers by The Number of 1 Bits

By zxi on February 22, 2020

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]

Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.

Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]

Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]

Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]

Constraints:

1 <= arr.length <= 500
0 <= arr[i] <= 10^4

Solution: Sorting

Time complexity: O(nlogn)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> sortByBits(vector<int>& arr) {

sort(begin(arr), end(arr), [](const int a, const int b){

int key_a = __builtin_popcount(a);

int key_b = __builtin_popcount(b);

if (key_a != key_b) return key_a < key_b;

return a < b;

});

return arr;

}

};

Python3

# Author: Huahua

class Solution:

def sortByBits(self, arr: List[int]) -> List[int]:

return sorted(arr, key=lambda x: (bin(x).count('1') << 16) + x)

花花酱 LeetCode 1318. Minimum Flips to Make a OR b Equal to c

By zxi on January 13, 2020

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation).
Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation.

Example 1:

Input: a = 2, b = 6, c = 5
Output: 3
Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c)

Example 2:

Input: a = 4, b = 2, c = 7
Output: 1

Example 3:

Input: a = 1, b = 2, c = 3
Output: 0

Constraints:

1 <= a <= 10^9
1 <= b <= 10^9
1 <= c <= 10^9

Solution: Bit operation

If the bit of c is 1, a / b at least has one 1. cost = 1 – ((a | b) & 1)
If the bit of c is 0, a / b must be 0, cost = (a & 1) + (b & 1)

Time complexity: O(32)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int minFlips(int a, int b, int c) {

int count = 0;

for (int i = 0; i < 32; ++i) {

if (c & 1) count += 1 - ((a | b) & 1);

else count += (a & 1) + (b & 1);

a >>= 1;

b >>= 1;

c >>= 1;

}

return count;

}

};

花花酱 LeetCode 1310. XOR Queries of a Subarray

By zxi on January 5, 2020

Given the array arr of positive integers and the array queries where queries[i] = [L_i,R_i], for each query i compute the XOR of elements from L_i to Ri (that is, arr[L_i] xor arr[L_i+1] xor ... xor arr[R_i] ). Return an array containing the result for the given queries.

Example 1:

Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8] 
Explanation: 
The binary representation of the elements in the array are:
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
The XOR values for queries are:
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

Example 2:

Input: arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]
Output: [8,0,4,4]

Constraints:

1 <= arr.length <= 3 * 10^4
1 <= arr[i] <= 10^9
1 <= queries.length <= 3 * 10^4
queries[i].length == 2
0 <= queries[i][0] <= queries[i][1] < arr.length

Solution: Prefix Sum

Time complexity: O(n) + O(q)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) {

// xors[i + 1] = arr[0] ^ arr[1] ^ ... ^ arr[i]

vector<int> xors(arr.size() + 1);

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

xors[i + 1] = xors[i] ^ arr[i];

}

vector<int> ans;

for (const auto& q : queries) {

const int l = q[0];

const int r = q[1];

ans.push_back(xors[r + 1] ^ xors[l]);

}

return ans;

}

};

tby

花花酱 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

By zxi on October 27, 2019

Given an array of strings arr. String s is a concatenation of a sub-sequence of arr which have unique characters.

Return the maximum possible length of s.

Example 1:

Input: arr = ["un","iq","ue"]
Output: 4
Explanation: All possible concatenations are "","un","iq","ue","uniq" and "ique".
Maximum length is 4.

Example 2:

Input: arr = ["cha","r","act","ers"]
Output: 6
Explanation: Possible solutions are "chaers" and "acters".

Example 3:

Input: arr = ["abcdefghijklmnopqrstuvwxyz"]
Output: 26

Constraints:

1 <= arr.length <= 16
1 <= arr[i].length <= 26
arr[i] contains only lower case English letters.

Solution: Combination + Bit

Time complexity: O(2^n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

set<char> s(begin(x), end(x));

if (s.size() != x.length()) continue;

a.push_back(0);

for (char c : x) a.back() |= 1 << (c - 'a');

}

int ans = 0;

function<void(int, int)> dfs = [&](int s, int cur) {

ans = max(ans, __builtin_popcount(cur));

for (int i = s; i < a.size(); ++i)

if ((cur & a[i]) == 0)

dfs(i + 1, cur | a[i]);

};

dfs(0, 0);

return ans;

}

};

Solution 2: DP

Time complexity: O(2^n)
Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

int maxLength(vector<string>& arr) {

vector<int> a;

for (const string& x : arr) {

int mask = 0;

for (char c : x) mask |= 1 << (c - 'a');

if (__builtin_popcount(mask) != x.length()) continue;

a.push_back(mask);

}

int ans = 0;

vector<int> dp{0};

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

int size = dp.size();

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

if (dp[j] & a[i]) continue;

int t = dp[j] | a[i];

dp.push_back(t);

ans = max(ans, __builtin_popcount(t));

}

return ans;

}

};

花花酱 LeetCode 1238. Circular Permutation in Binary Representation

By zxi on October 27, 2019

Given 2 integers n and start. Your task is return any permutation p of (0,1,2.....,2^n -1) such that :

p[0] = start
p[i] and p[i+1] differ by only one bit in their binary representation.
p[0] and p[2^n -1] must also differ by only one bit in their binary representation.

Example 1:

Input: n = 2, start = 3
Output: [3,2,0,1]
Explanation: The binary representation of the permutation is (11,10,00,01). 
All the adjacent element differ by one bit. Another valid permutation is [3,1,0,2]

Example 2:

Input: n = 3, start = 2
Output: [2,6,7,5,4,0,1,3]
Explanation: The binary representation of the permutation is (010,110,111,101,100,000,001,011).

Constraints:

1 <= n <= 16
0 <= start < 2 ^ n

Solution 1: Gray Code (DP) + Rotation

Gray code starts with 0, need to rotate after generating the list.

Time complexity: O(2^n)
Space complexity: O(2^n)

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

vector<vector<int>> dp(n + 1);

dp[0] = {0};

for (int i = 1; i <= n; ++i) {

dp[i] = dp[i - 1];

for (int j = dp[i - 1].size() - 1; j >= 0; --j)

dp[i].push_back(dp[i - 1][j] | (1 << (i - 1)));

}

for (auto it = begin(dp[n]); it != end(dp[n]); ++it)

if (*it == start) {

rotate(begin(dp[n]), it, end(dp[n]));

break;

}

return dp[n];

}

};

Solution 2: Gray code with a start

Time complexity: O(2^n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> circularPermutation(int n, int start) {

vector<int> ans(1 << n);

for (int i = 0; i < 1 << n; ++i)

ans[i] = start ^ i ^ i >> 1;

return ans;

}

};