Posts published in “Bit”

花花酱 LeetCode 1835. Find XOR Sum of All Pairs Bitwise AND

By zxi on April 18, 2021

The XOR sum of a list is the bitwise XOR of all its elements. If the list only contains one element, then its XOR sum will be equal to this element.

For example, the XOR sum of [1,2,3,4] is equal to 1 XOR 2 XOR 3 XOR 4 = 4, and the XOR sum of [3] is equal to 3.

You are given two 0-indexed arrays arr1 and arr2 that consist only of non-negative integers.

Consider the list containing the result of arr1[i] AND arr2[j] (bitwise AND) for every (i, j) pair where 0 <= i < arr1.length and 0 <= j < arr2.length.

Return the XOR sum of the aforementioned list.

Example 1:

Input: arr1 = [1,2,3], arr2 = [6,5]
Output: 0
Explanation: The list = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1].
The XOR sum = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0.

Example 2:

Input: arr1 = [12], arr2 = [4]
Output: 4
Explanation: The list = [12 AND 4] = [4]. The XOR sum = 4.

Constraints:

1 <= arr1.length, arr2.length <= 10⁵
0 <= arr1[i], arr2[j] <= 10⁹

Solution: Bit

(a[0] & b[i]) ^ (a[1] & b[i]) ^ … ^ (a[n-1] & b[i]) = (a[0] ^ a[1] ^ … ^ a[n-1]) & b[i]

We can pre compute that xor sum of array A.

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

C++

class Solution {

public:

int getXORSum(vector<int>& A, vector<int>& B) {

int ans = 0;

int xora = 0;

for (int a : A) xora ^= a;

for (int b : B) ans ^= (xora & b);

return ans;

}

};

花花酱 LeetCode 1829. Maximum XOR for Each Query

By zxi on April 17, 2021

You are given a sorted array nums of n non-negative integers and an integer maximumBit. You want to perform the following query n times:

Find a non-negative integer k < 2^maximumBit such that nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k is maximized. k is the answer to the i^th query.
Remove the last element from the current array nums.

Return an array answer, where answer[i] is the answer to the i^th query.

Example 1:

Input: nums = [0,1,1,3], maximumBit = 2
Output: [0,3,2,3]
Explanation: The queries are answered as follows:
1^st query: nums = [0,1,1,3], k = 0 since 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3.
2^nd query: nums = [0,1,1], k = 3 since 0 XOR 1 XOR 1 XOR 3 = 3.
3^rd query: nums = [0,1], k = 2 since 0 XOR 1 XOR 2 = 3.
4^th query: nums = [0], k = 3 since 0 XOR 3 = 3.

Example 2:

Input: nums = [2,3,4,7], maximumBit = 3
Output: [5,2,6,5]
Explanation: The queries are answered as follows:
1^st query: nums = [2,3,4,7], k = 5 since 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7.
2^nd query: nums = [2,3,4], k = 2 since 2 XOR 3 XOR 4 XOR 2 = 7.
3^rd query: nums = [2,3], k = 6 since 2 XOR 3 XOR 6 = 7.
4^th query: nums = [2], k = 5 since 2 XOR 5 = 7.

Example 3:

Input: nums = [0,1,2,2,5,7], maximumBit = 3
Output: [4,3,6,4,6,7]

Constraints:

nums.length == n
1 <= n <= 10⁵
1 <= maximumBit <= 20
0 <= nums[i] < 2^maximumBit
nums is sorted in ascending order.

Solution: Prefix XOR

Compute s = nums[0] ^ nums[1] ^ … nums[n-1] first

to remove nums[i], we just need to do s ^= nums[i]

We can always maximize the xor of s and k to (2^maxbit – 1)
k = (2 ^ maxbit – 1) ^ s

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

C++

// Author: Huahua

class Solution {

public:

vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {

const int t = (1 << maximumBit) - 1;

const int n = nums.size();

vector<int> ans(n);

int s = 0;

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

for (int i = n - 1; i >= 0; --i) {

ans[n - i - 1] = t ^ s;

s ^= nums[i];

}

return ans;

}

};

花花酱 LeetCode 1734. Decode XORed Permutation

By zxi on January 23, 2021

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

Example 1:

Input: encoded = [3,1]
Output: [1,2,3]
Explanation: If perm = [1,2,3], then encoded = [1 XOR 2,2 XOR 3] = [3,1]

Example 2:

Input: encoded = [6,5,4,6]
Output: [2,4,1,5,3]

Constraints:

3 <= n < 10⁵
n is odd.
encoded.length == n - 1

Solution: XOR

The key is to find p[0]. p[i] = p[i – 1] ^ encoded[i – 1]

p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
encoded[1] ^ encode[3] ^ … ^ encoded[n-2] = (p[1] ^ p[2]) ^ (p[3] ^ p[4]) ^ … ^ (p[n-2] ^ p[n-1])

1) xor 2) = p[0]

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

C++

// Author: Huahua

class Solution {

public:

vector<int> decode(vector<int>& encoded) {

const int n = encoded.size() + 1;

vector<int> perm(n);

// p[0] = (p[0]^p[1]^...^p[n-1] = 1^2^...^n)

// ^ (p[1]^p[2]^...^p[n-1])

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

perm[0] ^= i;

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

perm[0] ^= encoded[i];

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

perm[i] = perm[i - 1] ^ encoded[i - 1];

return perm;

}

};

花花酱 LeetCode 1720. Decode XORed Array

By zxi on January 10, 2021

There is a hidden integer array arr that consists of n non-negative integers.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].

You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].

Return the original array arr. It can be proved that the answer exists and is unique.

Example 1:

Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]

Example 2:

Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]

Constraints:

2 <= n <= 10⁴
encoded.length == n - 1
0 <= encoded[i] <= 10⁵
0 <= first <= 10⁵

Solution: XOR

encoded[i] = arr[i] ^ arr[i + 1]
encoded[i] ^ arr[i] = arr[i] ^ arr[i] ^ arr[i + 1]
arr[i+1] = encoded[i]^arr[i]

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

C++

class Solution {

public:

vector<int> decode(vector<int>& encoded, int first) {

const int n = encoded.size() + 1;

vector<int> ans(n, first);

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

ans[i + 1] = ans[i] ^ encoded[i];

return ans;

}

};

花花酱 LeetCode 1680. Concatenation of Consecutive Binary Numbers

By zxi on December 6, 2020

Given an integer n, return the decimal value of the binary string formed by concatenating the binary representations of 1 to n in order, modulo 10⁹+ 7.

Example 1:

Input: n = 1
Output: 1
Explanation: "1" in binary corresponds to the decimal value 1.

Example 2:

Input: n = 3
Output: 27
Explanation: In binary, 1, 2, and 3 corresponds to "1", "10", and "11".
After concatenating them, we have "11011", which corresponds to the decimal value 27.

Example 3:

Input: n = 12
Output: 505379714
Explanation: The concatenation results in "1101110010111011110001001101010111100".
The decimal value of that is 118505380540.
After modulo 10⁹ + 7, the result is 505379714.

Constraints:

1 <= n <= 10⁵

Solution: Bit Operation

f(n) = (f(n – 1) << length(n)) | n

length(n) increase by 1 whenever n is power of 2.
n = 1, YES, len = 1
n = 2, YES, len = 2
n = 3, NO, len = 2
n = 4, YES, len = 3
n = 5, NO, len = 3
n = 6, NO, len = 3
n = 7, NO, len = 3
n = 8, YES, len = 4
…

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

C++

// Author: Huahua

class Solution {

public:

int concatenatedBinary(int n) {

constexpr int kMod = 1e9 + 7;

long ans = 0;

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

if ((i & (i - 1)) == 0) ++len;

ans = ((ans << len) % kMod + i) % kMod;

}

return ans;

}

};