You are given a 0-indexed integer array nums and a positive integer k.
You can apply the following operation on the array any number of times:
0 to 1 or vice versa.Return the minimum number of operations required to make the bitwise XOR of all elements of the final array equal to k.
Note that you can flip leading zero bits in the binary representation of elements. For example, for the number (101)2 you can flip the fourth bit and obtain (1101)2.
Example 1:
Input: nums = [2,1,3,4], k = 1 Output: 2 Explanation: We can do the following operations: - Choose element 2 which is 3 == (011)2, we flip the first bit and we obtain (010)2 == 2. nums becomes [2,1,2,4]. - Choose element 0 which is 2 == (010)2, we flip the third bit and we obtain (110)2 = 6. nums becomes [6,1,2,4]. The XOR of elements of the final array is (6 XOR 1 XOR 2 XOR 4) == 1 == k. It can be shown that we cannot make the XOR equal to k in less than 2 operations.
Example 2:
Input: nums = [2,0,2,0], k = 0 Output: 0 Explanation: The XOR of elements of the array is (2 XOR 0 XOR 2 XOR 0) == 0 == k. So no operation is needed.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1060 <= k <= 106This approach involves using bit manipulation to find out which bits are different between the XOR of the array and k. For each differing bit, calculate the minimum number of flips needed across all elements to switch that bit in the resultant XOR.
We start by calculating the XOR sum of the array, XOR it with k to find the differing bits, and count each differing bit as an operation needed to make the elements' XOR equal to k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the array, since we only traverse it twice.
Space Complexity: O(1), as no additional data structures are used.
In this approach, the focus is on counting the set bits of two numbers (XOR sum and k) - i.e., how many bits are 1 in their binary representation. We aim to equalize the set bits count by flipping specific bits in nums.
We define a helper function to count the set bits of a number. We calculate XOR sum first, and then find the difference in set bit numbers compared to k.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + log(max(nums[i])))
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Bit Manipulation | Time Complexity: O(n), where n is the length of the array, since we only traverse it twice. |
| Approach 2: Count Set Bits | Time Complexity: O(n + log(max(nums[i]))) |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 views views
Watch 9 more video solutions →Practice Minimum Number of Operations to Make Array XOR Equal to K with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor