#2588
Count the Number of Beautiful Subarrays
specialist · 820 · lc medium +31 · verified · 53.4% accepted · 560 likes · top 44%
Description
You are given a 0-indexed integer array nums. An operation lets you pick two distinct indices i and j that both have a 1 at bit position k, then subtract 2k from both nums[i] and nums[j]. A subarray is beautiful if repeated operations can reduce all its elements to 0. Subarrays that are all zeros initially also count as beautiful. Return the count of beautiful subarrays. A subarray is a contiguous non-empty sequence.
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.
Code
1
2
3