Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Move from brute-force thinking to an efficient approach using array strategy.
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 (including zero).
Return the number of beautiful subarrays in the array nums.
A subarray is a contiguous non-empty sequence of elements within an array.
Note: Subarrays where all elements are initially 0 are considered beautiful, as no operation is needed.
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] <= 106Problem summary: 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 (including zero). Return the number of beautiful subarrays in the array nums. A subarray is a contiguous non-empty sequence of elements within an array. Note: Subarrays where all elements are initially 0 are considered beautiful, as no operation is needed.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Hash Map · Bit Manipulation
[4,3,1,2,4]
[1,10,4]
maximum-xor-for-each-query)count-the-number-of-ideal-arrays)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #2588: Count the Number of Beautiful Subarrays
class Solution {
public long beautifulSubarrays(int[] nums) {
Map<Integer, Integer> cnt = new HashMap<>();
cnt.put(0, 1);
long ans = 0;
int mask = 0;
for (int x : nums) {
mask ^= x;
ans += cnt.merge(mask, 1, Integer::sum) - 1;
}
return ans;
}
}
// Accepted solution for LeetCode #2588: Count the Number of Beautiful Subarrays
func beautifulSubarrays(nums []int) (ans int64) {
cnt := map[int]int{0: 1}
mask := 0
for _, x := range nums {
mask ^= x
ans += int64(cnt[mask])
cnt[mask]++
}
return
}
# Accepted solution for LeetCode #2588: Count the Number of Beautiful Subarrays
class Solution:
def beautifulSubarrays(self, nums: List[int]) -> int:
cnt = Counter({0: 1})
ans = mask = 0
for x in nums:
mask ^= x
ans += cnt[mask]
cnt[mask] += 1
return ans
// Accepted solution for LeetCode #2588: Count the Number of Beautiful Subarrays
use std::collections::HashMap;
impl Solution {
pub fn beautiful_subarrays(nums: Vec<i32>) -> i64 {
let mut cnt = HashMap::new();
cnt.insert(0, 1);
let mut ans = 0;
let mut mask = 0;
for &x in nums.iter() {
mask ^= x;
ans += *cnt.get(&mask).unwrap_or(&0);
*cnt.entry(mask).or_insert(0) += 1;
}
ans
}
}
// Accepted solution for LeetCode #2588: Count the Number of Beautiful Subarrays
function beautifulSubarrays(nums: number[]): number {
const cnt = new Map();
cnt.set(0, 1);
let ans = 0;
let mask = 0;
for (const x of nums) {
mask ^= x;
ans += cnt.get(mask) || 0;
cnt.set(mask, (cnt.get(mask) || 0) + 1);
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Sort the array in O(n log n), then scan for the missing or unique element by comparing adjacent pairs. Sorting requires O(n) auxiliary space (or O(1) with in-place sort but O(n log n) time remains). The sort step dominates.
Bitwise operations (AND, OR, XOR, shifts) are O(1) per operation on fixed-width integers. A single pass through the input with bit operations gives O(n) time. The key insight: XOR of a number with itself is 0, which eliminates duplicates without extra space.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.