You are given a 0-indexed integer array nums
. In one operation, you can:
- Choose two different indices
i
andj
such that0 <= i, j < nums.length
. - Choose a non-negative integer
k
such that thekth
bit (0-indexed) in the binary representation ofnums[i]
andnums[j]
is1
. - Subtract
2k
fromnums[i]
andnums[j]
.
A subarray is beautiful if it is possible to make all of its elements equal to 0
after applying the above operation any number of times.
Return the number of beautiful subarrays in the array nums
.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [4,3,1,2,4] Output: 2 Explanation: There are 2 beautiful subarrays in nums: [4,3,1,2,4] and [4,3,1,2,4]. - We can make all elements in the subarray [3,1,2] equal to 0 in the following way: - Choose [3, 1, 2] and k = 1. Subtract 21 from both numbers. The subarray becomes [1, 1, 0]. - Choose [1, 1, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 0, 0]. - We can make all elements in the subarray [4,3,1,2,4] equal to 0 in the following way: - Choose [4, 3, 1, 2, 4] and k = 2. Subtract 22 from both numbers. The subarray becomes [0, 3, 1, 2, 0]. - Choose [0, 3, 1, 2, 0] and k = 0. Subtract 20 from both numbers. The subarray becomes [0, 2, 0, 2, 0]. - Choose [0, 2, 0, 2, 0] and k = 1. Subtract 21 from both numbers. The subarray becomes [0, 0, 0, 0, 0].
Example 2:
Input: nums = [1,10,4] Output: 0 Explanation: There are no beautiful subarrays in nums.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 106
Solution: Hashtable + Prefix XOR
The problem is asking to find # of subarrays whose element wise xor is 0. We can use a hashtable to store the frequency of each prefix xor value, which reduces this problem to # of Subarray sum equal to k.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: long long beautifulSubarrays(vector<int>& nums) { long long ans = 0; unordered_map<int, int> m{{0, 1}}; int x = 0; for (int i = 0; i < nums.size(); ++i) { x ^= nums[i]; ans += m[x]; m[x] += 1; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment