Press "Enter" to skip to content

Posts tagged as “xor”

花花酱 LeetCode 1529. Bulb Switcher IV

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

花花酱 LeetCode 1486. XOR Operation in an Array

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

花花酱 LeetCode 1442. Count Triplets That Can Form Two Arrays of Equal XOR

Given an array of integers arr.

We want to select three indices ij and k where (0 <= i < j <= k < arr.length).

Let’s define a and b as follows:

  • a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
  • b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

Note that ^ denotes the bitwise-xor operation.

Return the number of triplets (ij and k) Where a == b.

Example 1:

Input: arr = [2,3,1,6,7]
Output: 4
Explanation: The triplets are (0,1,2), (0,2,2), (2,3,4) and (2,4,4)

Example 2:

Input: arr = [1,1,1,1,1]
Output: 10

Example 3:

Input: arr = [2,3]
Output: 0

Example 4:

Input: arr = [1,3,5,7,9]
Output: 3

Example 5:

Input: arr = [7,11,12,9,5,2,7,17,22]
Output: 8

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[i] <= 10^8

Solution 1: Brute Force (TLE)

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

C++

Solution 2: Prefix XORs

Let xors[i] = arr[0] ^ arr[1] ^ … ^ arr[i-1]
arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1] = (arr[0] ^ … ^ arr[j – 1]) ^ (arr[0] ^ … ^ arr[i-1]) = xors[j] ^ xors[i]

We then can compute a and b in O(1) time.

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

C++

Solution 3: Prefix XORs II

a = arr[i] ^ arr[i + 1] ^ … ^ arr[j – 1]
b = arr[j] ^ arr[j + 1] ^ … ^ arr[k]
a == b => a ^ b == 0
XORs(i ~ k) == 0
XORS(0 ~ k) ^ XORs(0 ~ i – 1) = 0

Problem => find all pairs of (i – 1, k) such that xors[k+1] == xors[i]
For each pair (i – 1, k), there are k – i positions we can insert j.

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

C++

Solution 3: HashTable

Similar to target sum, use a hashtable to store the frequency of each prefix xors.

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

C++

花花酱 LeetCode 1310. XOR Queries of a Subarray

Given the array arr of positive integers and the array queries where queries[i] = [Li, Ri], for each query i compute the XOR of elements from Li to Ri (that is, arr[Lixor arr[Li+1xor ... xor arr[Ri] ). 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++

tby

花花酱 LeetCode 1252. Cells with Odd Values in a Matrix

Given n and m which are the dimensions of a matrix initialized by zeros and given an array indices where indices[i] = [ri, ci]. For each pair of [ri, ci] you have to increment all cells in row ri and column ci by 1.

Return the number of cells with odd values in the matrix after applying the increment to all indices.

Example 1:

Input: n = 2, m = 3, indices = [[0,1],[1,1]]
Output: 6
Explanation: Initial matrix = [[0,0,0],[0,0,0]].
After applying first increment it becomes [[1,2,1],[0,1,0]].
The final matrix will be [[1,3,1],[1,3,1]] which contains 6 odd numbers.

Example 2:

Input: n = 2, m = 2, indices = [[1,1],[0,0]]
Output: 0
Explanation: Final matrix = [[2,2],[2,2]]. There is no odd number in the final matrix.

Constraints:

  • 1 <= n <= 50
  • 1 <= m <= 50
  • 1 <= indices.length <= 100
  • 0 <= indices[i][0] < n
  • 0 <= indices[i][1] < m

Solution 1: Simulation

Time complexity: O((n+m)*k + n*m)
Space complexity: O(n*m)

C++

Solution 2: Counting

For each row and column, compute how many times it will be increased (odd or even).
For each a[i][j], check how many times the i-th row and j-th column were increased, if the sum is odd then a[i][j] will odd.
Time complexity: O(n*m + k)
Space complexity: O(n+m)

C++