Press "Enter" to skip to content

Posts tagged as “xor”

花花酱 LeetCode 1738. Find Kth Largest XOR Coordinate Value

You are given a 2D matrix of size m x n, consisting of non-negative integers. You are also given an integer k.

The value of coordinate (a, b) of the matrix is the XOR of all matrix[i][j] where 0 <= i <= a < m and 0 <= j <= b < n (0-indexed).

Find the kth largest value (1-indexed) of all the coordinates of matrix.

Example 1:

Input: matrix = [[5,2],[1,6]], k = 1
Output: 7
Explanation: The value of coordinate (0,1) is 5 XOR 2 = 7, which is the largest value.

Example 2:

Input: matrix = [[5,2],[1,6]], k = 2
Output: 5
Explanation: The value of coordinate (0,0) is 5 = 5, which is the 2nd largest value.

Example 3:

Input: matrix = [[5,2],[1,6]], k = 3
Output: 4
Explanation: The value of coordinate (1,0) is 5 XOR 1 = 4, which is the 3rd largest value.

Example 4:

Input: matrix = [[5,2],[1,6]], k = 4
Output: 0
Explanation: The value of coordinate (1,1) is 5 XOR 2 XOR 1 XOR 6 = 0, which is the 4th largest value.

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 1000
  • 0 <= matrix[i][j] <= 106
  • 1 <= k <= m * n

Solution: DP

Similar to 花花酱 LeetCode 304. Range Sum Query 2D – Immutable

xor[i][j] = matrix[i][j] ^ xor[i – 1][j – 1] ^ xor[i – 1][j] ^ xor[i][j- 1]

Time complexity: O(mn)
Space complexity: O(mn)

C++

花花酱 LeetCode 1734. Decode XORed Permutation

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 < 105
  • n is odd.
  • encoded.length == n - 1

Solution: XOR

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

  1. p[0] ^ p[1] ^ … ^ p[n-1] = 1 ^ 2 ^ … ^ n
  2. 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++

花花酱 LeetCode 1720. Decode XORed Array

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 <= 104
  • encoded.length == n - 1
  • 0 <= encoded[i] <= 105
  • 0 <= first <= 105

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++

花花酱 LeetCode 421. Maximum XOR of Two Numbers in an Array

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 * 104
  • 0 <= nums[i] <= 231 - 1

Solution: Trie

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

C++

花花酱 LeetCode 1542. Find Longest Awesome Substring

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++

Java

Python3