1787. Make the XOR of All Segments Equal to Zero

HardBit ManipulationArrayDynamic Programming

Problem Description

The problem presents us with an array nums and an integer k, where we are interested in the XOR of segments of the array. Each segment has a size of k, meaning it includes k consecutive elements from the array. The XOR of a segment [left, right] is the result of performing the XOR operation on all elements from index left to index right, inclusive.

We are tasked with finding the minimum number of elements we must change in the original array so that the XOR of all possible segments of size k will be equal to zero.

To put it in simple terms, we need to make modifications to the array such that when you take any k consecutive elements and do an XOR operation on them, the result should always be zero, no matter where you start in the array. The goal is to achieve this by making as few changes to the array elements as possible.

Intuition

The intuition behind the solution involves dynamic programming and bit manipulation.

We start by considering that the XOR operation has a unique property where a XOR a = 0 for any number a. Therefore, for the XOR of a segment to be zero, we can think of pairing equal numbers within the segment.

However, instead of trying to sort out pairs directly, we use dynamic programming to keep track of the minimum number of changes needed for each possible XOR result of segments we've processed so far.

More explicitly, the following points guide our intuition:

We notice that the array's elements are nums, and since array values are integers, a 10-bit number can represent them (hence n = 1 << 10 is to declare the possible XOR results range, as 2^10 = 1024).
We break down the problem by considering each position modulo k. If two elements are at positions i and j such that i % k == j % k, they will be in the same positions within their respective segments of length k. By focusing on these groups, we simplify our problem to k smaller problems.
We count occurrences of each element in these positions (modulo k), which helps us identify the most frequent elements that contribute to the current XOR value.
We construct the f array, where f[i] represents the minimum number of changes needed to make the XOR of all processed segments equal to i. Initially, f[0] is 0 because no changes are needed to keep the XOR of an empty segment as zero.
We then iterate through the k groups and update the f array for each group. For each XOR value j, we compute g[j] as either the minimum number of changes from f plus the size of the group (if we decide to change all elements in the current group) or f[j XOR v] plus the size of the group minus the count of v in the current group (if we decide to keep v and thus do not need to change the elements equal to v).
We use inf to represent a large number as initialization because we want to calculate the minimum changes, and we need an upper limit to start the comparison.
Finally, f[0] gives us the answer to the problem after considering all groups, which is the minimum number of changes required to ensure the XOR of all segments of size k equals to zero.

The solution is ingenious because it combines dynamic programming (to keep track of the 'state' of our solution as we process each group) with the algebraic properties of XOR (like commutativity and given any number a, a XOR a = 0). It's this combination that allows us to solve the problem efficiently.

Learn more about Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right<, left, right<=, right, left<, right, left

I don’t know

Solution Approach

The solution to the problem follows a dynamic programming approach with bit manipulation techniques. Below is a step-by-step explanation of how the solution works:

Initialization: We start by initializing an array f of length n (which is 1 << 10, representing all possible XOR values for 10-bit numbers). Initially, it is filled with inf (infinity) to indicate that we haven't made any changes yet. f[0] is set to 0 as the base case because the XOR of an empty segment is 0.
Counting Elements per Group: We then create a list of Counter objects, cnt, one for each of the k groups (where each group corresponds to positions in the array that are equivalent modulo k). We also maintain a size array that tracks the number of elements in each group. We iterate through the nums array, grouping the elements by their position modulo k, and increment their count in the corresponding Counter. This sets up our frequency table to identify which elements are most common in each group.
Iterating Over Groups: Now we apply dynamic programming. For each of the k groups, we create a temporary g array (similar to f, also of length n) that represents the state of our dynamic programming after processing the current group.
DP Updates: For each value j from 0 to n-1, we determine the new minimum number of changes g[j], which is initially set to the minimum value of the previous state f plus the number of elements in the current group (size[i]). This represents changing all elements in the current group to get the XOR value j.
Iterating Over XOR combinations: However, because we can possibly retain some elements without changing them (to potentially lower the count), we iterate over the current group's elements. For each element v and its count c, we compare g[j] with f[j ^ v] + size[i] - c. Here's the reasoning:
- The j ^ v operation computes the previous XOR state required to transition to j when v is included in the XOR computation.
- f[j ^ v] retrieves the minimum number of changes needed for that previous state.
- size[i] - c accounts for the elements in the group that we need to change, other than those equal to v.
Updating Current State: The minimum value computed for g[j] is then assigned, reflecting the minimum number of changes after considering the current group.
Transitioning States: After processing all elements in the given group, we copy the state from g to f. This step is crucial as it updates the dynamic programming state to include the decisions made for the current group.
Result: Upon processing all k groups, f[0] will hold the minimum number of changes we need to make to ensure that the XOR of every segment of size k is zero, because f[0] represents the XOR value for the entire array segment (in our case, we want it to be zero).

In terms of algorithms and patterns, the key aspects of the solution are the utilization of dynamic programming to track collective states across different segments and bit manipulation to efficiently handle the XOR operations and state transitions. The implementation also makes good use of Python's built-in Counter class to track frequencies of elements, allowing for a cleaner and more efficient solution.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example Walkthrough

Let's say we have the following input array nums = [1, 2, 3, 4, 5] and k = 2. According to our problem, we need to determine the minimum number of changes to make such that every segment of size k has an XOR total of zero.

With k = 2, we have the following segments to consider:

Segment 1: [1, 2] with XOR = 1 XOR 2
Segment 2: [2, 3] with XOR = 2 XOR 3
Segment 3: [3, 4] with XOR = 3 XOR 4
Segment 4: [4, 5] with XOR = 4 XOR 5

We will break down the example using the step-by-step approach described in the solution:

Initialization

First, we initialize our dynamic programming array f with a length of 1 << 10 (to cover all 10-bit numbers), all set to infinity, except for f[0] which is 0.

Counting Elements per Group

We now make our k groups based on the elements' positions modulo k:

Group 1 (positions modulo k = 0): [1, 3, 5]
Group 2 (positions modulo k = 1): [2, 4]

We use Counter objects to track the frequency of elements in each group:

Counter for Group 1: {1: 1, 3: 1, 5: 1}
Counter for Group 2: {2: 1, 4: 1}

We also have a size array indicating each group's size: [3, 2].

Iterating Over Groups and DP Updates

We iterate over each group, updating our DP array f to g. For simplicity, let's focus on Group 1 updates.

For Group 1, let's walk through the XOR combinations:

We consider the current XOR state (let's say j=0) and aim to achieve g[0].
Initially, g[0] is f[0] + size[0] = 0 + 3 = 3 because we assume we change all elements.
We iterate through the Counter and find that no element helps us reduce g[0] from 3 as including either 1, 3, or 5 would not reduce the total changes needed.

Now we would proceed to Group 2 and follow a similar approach, updating our g array considering the elements 2 and 4. For this simple example, however, there are no combinations that would lead to a segment XOR of zero without changing all elements, so our final f[0] after considering both groups would be the sum of sizes for both groups (3 + 2) minus any possible reductions, which in this case, are none.

Result

After processing both groups, f[0] holds the value 5, which is the minimum number of changes needed to ensure the XOR of all segments of size k is zero. However, since there were no elements to help reduce this number in our example, we find that all elements would have to be changed.

In a more complex example, we would have potential elements within the groups that when included in the XOR operations, would result in the previous XOR state plus the element being zero. This would reduce the count needed, and thus the number of changes required. But for our example, no such elements were present.

Solution Implementation

1from collections import Counter
2from math import inf
3
4class Solution:
5    def minChanges(self, nums: List[int], k: int) -> int:
6        # Initialize variables
7        max_xor_val = 1 << 10  # 2^10, since nums[i] is within [0, 1023]
8        counters = [Counter() for _ in range(k)]
9        each_group_size = [0] * k
10      
11        # Count the occurrences of each value in nums at each position modulo k
12        for index, value in enumerate(nums):
13            counters[index % k][value] += 1
14            each_group_size[index % k] += 1
15      
16        # Initialize the dynamic programming table with infinity
17        dp_table = [inf] * max_xor_val
18        dp_table[0] = 0  # Base case: xoring zero with anything gives that thing.
19      
20        # Iterate over each group (each position modulo k)
21        for group_index in range(k):
22            # Copy of the dp_table with added size to each element, representing min changes required.
23            next_dp_table = [min(dp_table) + each_group_size[group_index]] * max_xor_val
24          
25            # Iterate through all possible XOR values
26            for xor_value in range(max_xor_val):
27                # Update dp for next group considering all values in this group
28                for value, count in counters[group_index].items():
29                    next_dp_table[xor_value] = min(
30                        next_dp_table[xor_value], 
31                        dp_table[xor_value ^ value] + each_group_size[group_index] - count
32                    )
33          
34            # Move to the next dp table
35            dp_table = next_dp_table
36      
37        # Return the minimum changes needed for the whole array to have a constant xor value
38        return dp_table[0]
39

1class Solution {
2    public int minChanges(int[] nums, int k) {
3        // The maximum XOR value for 10 bits is 1024 (2^10)
4        final int MAX_XOR = 1 << 10;
5      
6        // Create an array of maps to count the occurrence of each number in each group
7        Map<Integer, Integer>[] countGroups = new Map[k];
8        // This array holds the size of each group
9        int[] groupSizes = new int[k];
10      
11        // Initialize the countGroups array
12        for (int i = 0; i < k; ++i) {
13            countGroups[i] = new HashMap<>();
14        }
15      
16        // Loop through the array and count occurrences
17        for (int i = 0; i < nums.length; ++i) {
18            countGroups[i % k].put(nums[i], countGroups[i % k].getOrDefault(nums[i], 0) + 1);
19            groupSizes[i % k]++;
20        }
21      
22        // f[i] will hold the minimum number of changes needed to have XOR of the new array equal to i
23        int[] changesNeededForXor = new int[MAX_XOR];
24        Arrays.fill(changesNeededForXor, Integer.MAX_VALUE);
25        changesNeededForXor[0] = 0;
26      
27        // Iterate over the groups
28        for (int i = 0; i < k; ++i) {
29            int[] newChanges = new int[MAX_XOR];
30            Arrays.fill(newChanges, min(changesNeededForXor) + groupSizes[i]);
31          
32            for (int xor = 0; xor < MAX_XOR; ++xor) {
33                for (var entry : countGroups[i].entrySet()) {
34                    int value = entry.getKey(), count = entry.getValue();
35                    // Update the number of changes needed for each XOR value
36                    newChanges[xor] = Math.min(newChanges[xor], changesNeededForXor[xor ^ value] + groupSizes[i] - count);
37                }
38            }
39          
40            changesNeededForXor = newChanges;
41        }
42      
43        // The answer is the minimum number of changes needed to have XOR of the new array equal to 0
44        return changesNeededForXor[0];
45    }
46
47    // Helper method to find the minimum value in an array
48    private int min(int[] arr) {
49        int minValue = arr[0];
50        for (int value : arr) {
51            minValue = Math.min(minValue, value);
52        }
53        return minValue;
54    }
55}
56

1class Solution {
2public:
3    int minChanges(vector<int>& nums, int k) {
4        // Maximum XOR value for numbers with 10 bits (1024 values from 0 to 1023).
5        const int max_xor = 1 << 10;
6
7        // Counters and sizes for each modulo class of k.
8        vector<unordered_map<int, int>> count(k);
9        vector<int> group_sizes(k);
10
11        // Populate the counters and sizes.
12        for (int i = 0; i < nums.size(); ++i) {
13            count[i % k][nums[i]]++;
14            group_sizes[i % k]++;
15        }
16
17        // Initialize a dynamic programming array with high initial values.
18        vector<int> dp(max_xor, INT_MAX / 2);
19        // Base case: 0 changes required to achieve a XOR of 0.
20        dp[0] = 0;
21
22        // Iterate over each modulo class.
23        for (int i = 0; i < k; ++i) {
24            // Find the smallest value in dp array.
25            int min_dp_value = *min_element(dp.begin(), dp.end());
26
27            // Create a new DP array for the following iteration.
28            vector<int> next_dp(max_xor, min_dp_value + group_sizes[i]);
29
30            // Update the next_dp values considering each value in the current group.
31            for (int j = 0; j < max_xor; ++j) {
32                for (const auto& value_count_pair : count[i]) {
33                    int value = value_count_pair.first;
34                    int cnt = value_count_pair.second;
35
36                    // Calculate the minimum changes for current XOR 'j'
37                    // by considering changing the current group values 'value' to achieve it.
38                    next_dp[j] = min(next_dp[j], dp[j ^ value] + group_sizes[i] - cnt);
39                }
40            }
41
42            // Move the updated array into dp for the next iteration.
43            dp = move(next_dp);
44        }
45
46        // Return the minimum changes required to achieve XOR of 0.
47        return dp[0];
48    }
49};
50

1// The maximum XOR value for numbers with 10 bits (1024 values from 0 to 1023).
2const MAX_XOR = 1 << 10;
3
4// Function to count the frequency of each number in each group modulo k.
5function countGroups(nums: number[], k: number): {count: Map<number, number>[], groupSizes: number[]} {
6    let count: Map<number, number>[] = new Array(k).fill(0).map(() => new Map<number, number>());
7    let groupSizes: number[] = new Array(k).fill(0);
8
9    // Populate the counters and group sizes.
10    nums.forEach((num, i) => {
11        let groupIndex = i % k;
12        count[groupIndex].set(num, (count[groupIndex].get(num) || 0) + 1);
13        groupSizes[groupIndex]++;
14    });
15
16    return { count, groupSizes };
17}
18
19// Function to calculate the minimum changes needed to make all XOR of all subarrays of length k to be 0.
20function minChanges(nums: number[], k: number): number {
21    let { count, groupSizes } = countGroups(nums, k);
22    let dp = new Array(MAX_XOR).fill(Number.MAX_SAFE_INTEGER / 2);
23    dp[0] = 0;
24
25    // Iterate over each modulo class.
26    for (let i = 0; i < k; ++i) {
27        // Find the smallest value in the dp array.
28        let minDpValue = Math.min(...dp);
29
30        // Create a new DP array for the next iteration.
31        let nextDp = new Array(MAX_XOR).fill(minDpValue + groupSizes[i]);
32
33        // Update the nextDp values considering each value in the current group.
34        for (let j = 0; j < MAX_XOR; ++j) {
35            count[i].forEach((cnt, value) => {
36                // Calculate the minimum changes for current XOR 'j'
37                // by considering changing the current group values 'value' to achieve it.
38                nextDp[j] = Math.min(nextDp[j], dp[j ^ value] + groupSizes[i] - cnt);
39            });
40        }
41
42        // Move the updated array into dp for the next iteration.
43        dp = nextDp;
44    }
45
46    // Return the minimum changes required to achieve XOR of 0.
47    return dp[0];
48}
49

Not Sure What to Study? Take the 2-min Quiz：

Depth first search can be used to find whether two components in a graph are connected.

TrueFalse

I don’t know

Time and Space Complexity

Time Complexity

The given code consists of nested loops and recursive dictionary operations. The time complexity of the code is determined by several factors:

Outer Loop Over k: There is an outer loop which iterates k times, where k is the length of the sequence.
Inner Loop Over n: Within the outer loop, there is an inner loop that iterates n times, where n is a constant 1 << 10 (i.e., 1024 since we are considering 10-bit numbers).
Innermost Loop Over the Items in cnt[i]: For each value of j in the inner loop, the code iterates over the items in cnt[i], which could, in the worst-case, be O(n) due to possibility of all nums being distinct.
Min Function: The min(f) function operates over the entire f list, which is O(n).

Combining these factors, the worst-case time complexity is O(k * n * (n + min(f))). Since min(f) is called n times within the inner loop over n, this part dominates and we can simplify to O(k * n^2).

Space Complexity

The space complexity is primarily due to the storage requirements of the list f, list g, and cnt with its counters. Here are the considerations:

List f and g: Both have a size of n, yielding a O(n) space complexity.
List of Counters cnt: cnt is a list of k counters, and each counter in the worst case could have up to n distinct entries (if every number in the sequence was unique and less than 1024). In such a case, each counter would have a space complexity of O(n), totaling to O(k * n) for all k counters.

Combining the space complexities for f, g, and cnt gives a total space complexity of O(k * n + n) which simplifies to O(k * n) since n is a constant 1024 and typically we expect k to be within a closer magnitude to n rather than significantly larger.

Thus, the final space complexity is O(k * n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1787. Make the XOR of All Segments Equal to Zero

Problem Description

Intuition

Solution Approach

Example Walkthrough

Initialization

Counting Elements per Group

Iterating Over Groups and DP Updates

Result

Solution Implementation

Time and Space Complexity