Posts tagged as “xor”

花花酱 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 421. Maximum XOR of Two Numbers in an Array

By zxi on December 27, 2020

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Follow up: Could you do this in O(n) runtime?

Example 1:

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example 2:

Input: nums = [0]
Output: 0

Example 3:

Input: nums = [2,4]
Output: 6

Example 4:

Input: nums = [8,10,2]
Output: 10

Example 5:

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Constraints:

1 <= nums.length <= 2 * 10⁴
0 <= nums[i] <= 2³¹ - 1

Solution: Trie

Time complexity: O(31*2*n)
Space complexity: O(31*2*n)

C++

// Author: Huahua

class Trie {

public:

Trie(): children(2) {}

vector<unique_ptr<Trie>> children;

};

class Solution {

public:

int findMaximumXOR(vector<int>& nums) {

Trie root;

// Insert a number into the trie.

auto insert = [&](Trie* node, int num) {

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (!node->children[bit])

node->children[bit] = std::make_unique<Trie>();

node = node->children[bit].get();

}

};

// Find max xor sum of num and another element in the array.

auto query = [&](Trie* node, int num) {

int sum = 0;

for (int i = 31; i >= 0; --i) {

int bit = (num >> i) & 1;

if (node->children[1 - bit]) {

sum += (1 << i);

node = node->children[1 - bit].get();

} else {

node = node->children[bit].get();

}

return sum;

};

// Insert all numbers.

for (int x : nums)

insert(&root, x);

int ans = 0;

// For each number find the maximum xor sum.

for (int x : nums)

ans = max(ans, query(&root, x));

return ans;

}

};

花花酱 LeetCode 1542. Find Longest Awesome Substring

By zxi on August 10, 2020

Given a string s. An awesome substring is a non-empty substring of s such that we can make any number of swaps in order to make it palindrome.

Return the length of the maximum length awesome substring of s.

Example 1:

Input: s = "3242415"
Output: 5
Explanation: "24241" is the longest awesome substring, we can form the palindrome "24142" with some swaps.

Example 2:

Input: s = "12345678"
Output: 1

Example 3:

Input: s = "213123"
Output: 6
Explanation: "213123" is the longest awesome substring, we can form the palindrome "231132" with some swaps.

Example 4:

Input: s = "00"
Output: 2

Constraints:

1 <= s.length <= 10^5
s consists only of digits.

Solution: Prefix mask + Hashtable

For a palindrome all digits must occurred even times expect one. We can use a 10 bit mask to track the occurrence of each digit for prefix s[0~i]. 0 is even, 1 is odd.

We use a hashtable to track the first index of each prefix state.
If s[0~i] and s[0~j] have the same state which means every digits in s[i+1~j] occurred even times (zero is also even) and it’s an awesome string. Then (j – (i+1) + 1) = j – i is the length of the palindrome. So far so good.

But we still need to consider the case when there is a digit with odd occurrence. We can enumerate all possible ones from 0 to 9, and temporarily flip the bit of the digit and see whether that state happened before.

fisrt_index[0] = -1, first_index[*] = inf
ans = max(ans, j – first_index[mask])

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

C++

class Solution {

public:

int longestAwesome(string s) {

constexpr int kInf = 1e9;

vector<int> idx(1024, kInf);

idx[0] = -1;

int mask = 0; // prefix's state 0:even, 1:odd

int ans = 0;

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

mask ^= (1 << (s[i] - '0'));

ans = max(ans, i - idx[mask]);

// One digit with odd count is allowed.

for (int j = 0; j < 10; ++j)

ans = max(ans, i - idx[mask ^ (1 << j)]);

idx[mask] = min(idx[mask], i);

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

public int longestAwesome(String s) {

final int n = s.length();

int[] idx = new int[1024];

Arrays.fill(idx, n);

idx[0] = -1;

int mask = 0;

int ans = 0;

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

mask ^= (1 << (s.charAt(i) - '0'));

ans = Math.max(ans, i - idx[mask]);

for (int j = 0; j < 10; ++j)

ans = Math.max(ans,

i - idx[mask ^ (1 << j)]);

idx[mask] = Math.min(idx[mask], i);

}

return ans;

}

Python3

# Author: Huahua

class Solution:

def longestAwesome(self, s: str) -> int:

idx = [-1] + [len(s)] * 1023

ans, mask = 0, 0

for i, c in enumerate(s):

mask ^= 1 << (ord(c) - ord('0'))

ans = max([ans, i - idx[mask]]

+ [i - idx[mask ^ (1 << j)] for j in range(10)])

idx[mask] = min(idx[mask], i)

return ans

花花酱 LeetCode 1529. Bulb Switcher IV

By zxi on July 26, 2020

There is a room with n bulbs, numbered from 0 to n-1, arranged in a row from left to right. Initially all the bulbs are turned off.

Your task is to obtain the configuration represented by target where target[i] is ‘1’ if the i-th bulb is turned on and is ‘0’ if it is turned off.

You have a switch to flip the state of the bulb, a flip operation is defined as follows:

Choose any bulb (index i) of your current configuration.
Flip each bulb from index i to n-1.

When any bulb is flipped it means that if it is 0 it changes to 1 and if it is 1 it changes to 0.

Return the minimum number of flips required to form target.

Example 1:

Input: target = "10111"
Output: 3
Explanation: Initial configuration "00000".
flip from the third bulb:  "00000" -> "00111"
flip from the first bulb:  "00111" -> "11000"
flip from the second bulb:  "11000" -> "10111"
We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"
Output: 3
Explanation: "000" -> "111" -> "100" -> "101".

Example 3:

Input: target = "00000"
Output: 0

Example 4:

Input: target = "001011101"
Output: 5

Constraints:

1 <= target.length <= 10^5
target[i] == '0' or target[i] == '1'

Solution: XOR

Flip from left to right, since flipping the a bulb won’t affect anything in the left.
We count how many times flipped so far, and that % 2 will be the state for all the bulb to the right.
If the current bulb’s state != target, we have to flip once.

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

C++

class Solution {

public:

int minFlips(string target) {

int ans = 0;

int cur = 0;

for (char c : target) {

if (c - '0' != cur) {

cur ^= 1;

++ans;

}

return ans;

}

};

花花酱 LeetCode 1486. XOR Operation in an Array

By zxi on June 20, 2020

Given an integer n and an integer start.

Define an array nums where nums[i] = start + 2*i (0-indexed) and n == nums.length.

Return the bitwise XOR of all elements of nums.

Example 1:

Input: n = 5, start = 0
Output: 8
Explanation: Array nums is equal to [0, 2, 4, 6, 8] where (0 ^ 2 ^ 4 ^ 6 ^ 8) = 8.
Where "^" corresponds to bitwise XOR operator.

Example 2:

Input: n = 4, start = 3
Output: 8
Explanation: Array nums is equal to [3, 5, 7, 9] where (3 ^ 5 ^ 7 ^ 9) = 8.

Example 3:

Input: n = 1, start = 7
Output: 7

Example 4:

Input: n = 10, start = 5
Output: 2

Constraints:

1 <= n <= 1000
0 <= start <= 1000
n == nums.length

Solution: Simulation

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

C++

// Author: Huahua

class Solution {

public:

int xorOperation(int n, int start) {

int ans = 0;

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

ans ^= (start + 2 * i);

return ans;

}

};