2588. Count the Number of Beautiful Subarrays LeetCode Solution
In this guide, you will get 2588. Count the Number of Beautiful Subarrays LeetCode Solution with the best time and space complexity. The solution to Count the Number of Beautiful Subarrays problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Count the Number of Beautiful Subarrays
You are given a 0-indexed integer array nums. In one operation, you can:
Choose two different indices i and j such that 0 <= i, j < nums.length.
Choose a non-negative integer k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.
Subtract 2k from nums[i] and nums[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].
Input: nums = [1,10,4]
Output: 0
Explanation: There are no beautiful subarrays in nums.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 106
Complexity Analysis
Time Complexity:
Space Complexity:
2588. Count the Number of Beautiful Subarrays LeetCode Solution in C++
class Solution {
public:
long long beautifulSubarrays(vector<int>& nums) {
// A subarray is beautiful if xor(subarray) = 0.
long ans = 0;
int prefix = 0;
unordered_map<int, int> prefixCount{{0, 1}};
for (const int num : nums) {
prefix ^= num;
ans += prefixCount[prefix]++;
}
return ans;
}
}; /* code provided by PROGIEZ */
2588. Count the Number of Beautiful Subarrays LeetCode Solution in Java
class Solution {
public long beautifulSubarrays(int[] nums) {
// A subarray is beautiful if xor(subarray) = 0.
long ans = 0;
int prefix = 0;
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1);
for (final int num : nums) {
prefix ^= num;
ans += prefixCount.getOrDefault(prefix, 0);
prefixCount.merge(prefix, 1, Integer::sum);
}
return ans;
}
} // code provided by PROGIEZ
2588. Count the Number of Beautiful Subarrays LeetCode Solution in Python
class Solution:
def beautifulSubarrays(self, nums: list[int]) -> int:
# A subarray is beautiful if xor(subarray) = 0.
ans = 0
prefix = 0
prefixCount = collections.Counter({0: 1})
for num in nums:
prefix ^= num
ans += prefixCount[prefix]
prefixCount[prefix] += 1
return ans # code by PROGIEZ
