Watch 10 video solutions for Count the Number of Beautiful Subarrays, a medium level problem involving Array, Hash Table, Bit Manipulation. This walkthrough by NeetCodeIO has 12,544 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums. In one operation, you can:
i and j such that 0 <= i, j < nums.length.k such that the kth bit (0-indexed) in the binary representation of nums[i] and nums[j] is 1.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].
Example 2:
Input: nums = [1,10,4] Output: 0 Explanation: There are no beautiful subarrays in nums.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 106