Count the Number of Beautiful Subarrays - Practice Coding Problems

Count the Number of Beautiful Subarrays - Problem

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 2^k 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [4,2,4,2,3,1]

› Output: 8

💡 Note: Beautiful subarrays: [4,2,4,2], [2,4], [4,2], [2,4,2,3,1], [2], [4], [2], [3,1]. All have XOR = 0, meaning all bits can be paired and eliminated.

Example 2 — Single Elements

$ Input: nums = [1,10,4]

› Output: 0

💡 Note: No subarrays have XOR = 0. Each single element has non-zero XOR, and combinations like [1,10], [10,4], [1,10,4] all have non-zero XOR.

Example 3 — All Zeros

$ Input: nums = [0,0,0]

› Output: 6

💡 Note: All subarrays are beautiful since they contain only zeros: [0], [0], [0], [0,0], [0,0], [0,0,0]. Each has XOR = 0.

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array with integer elements

Find XOR = 0

Identify subarrays where XOR of all elements equals 0

Count Beautiful

Count all such subarrays as beautiful

Key Takeaway

🎯 Key Insight: A subarray is beautiful if its XOR equals 0, enabling perfect bit pairing

Asked in

G Google 12 M Microsoft 8 a Amazon 6

The key insight is that a subarray is beautiful if and only if its XOR equals 0, since the operation can eliminate pairs of identical bits. The optimal approach uses prefix XOR with hash map to find all subarrays with XOR = 0 in O(n) time. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized - Running XOR	O(n²)	O(1)	Calculate XOR incrementally while generating subarrays
Brute Force - Check All Subarrays	O(n³)	O(1)	Generate all subarrays and check if each can be made beautiful
Prefix XOR with Hash Map	O(n)	O(n)	Use prefix XOR and hash map to find beautiful subarrays in O(n) time

Optimized - Running XOR — Algorithm Steps

For each starting position, maintain running XOR
Extend subarray one element at a time
Update XOR incrementally and check if it equals 0

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Fix starting position of subarray

Extend & Update

Extend subarray and update XOR incrementally

Check Beautiful

Count when running XOR equals 0

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* nums, int n) {
    long long count = 0;
    
    // For each starting position
    for (int i = 0; i < n; i++) {
        int xorVal = 0;
        // Extend subarray from position i
        for (int j = i; j < n; j++) {
            xorVal ^= nums[j];  // Add current element to running XOR
            if (xorVal == 0) {  // Check if current subarray [i,j] is beautiful
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [a,b,c] format
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    long long result = solution(nums, n);
    printf("%lld\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops to generate all subarrays, but XOR calculated in O(1) per subarray

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables for running XOR

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized - Running XOR — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler