Windows With Zero XOR

Hard

You are given an array of non-negative codes codes and a window width width. A *window* is width consecutive elements of the array; there are len(codes) - width + 1 windows in total. One change writes any non-negative integer into any element of the array. The goal is for the bitwise XOR of the elements of every window to be 0. Return the minimum number of changes.

Example 1

codes=[6, 3, 5, 6, 3, 1], width=3 → 1

The windows [6, 3, 5], [3, 5, 6] and [5, 6, 3] already give 0, but the last window [6, 3, 1] gives 4. Changing the last number to 5 fixes it with one change.

Example 2

codes=[7, 0, 4], width=1 → 2

With width 1 each window is a single number, so every number must become 0. Both 7 and 4 have to change.

Example 3

codes=[1, 2, 3, 1, 2, 3, 1], width=3 → 0

1 XOR 2 XOR 3 = 0, and every window of three consecutive numbers holds exactly 1, 2 and 3, so nothing needs to change.

Constraints

1 ≤ width ≤ len(codes) ≤ 2000
0 ≤ codes[i] < 1024

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Array Dynamic Programming

Similar problems

Settle Up in the Fewest Transfers Hard Two Groups With the Same Average Hard Assembling Fragments Hard Square-Sum Chains Hard Smallest Team With Every Skill Hard

Input

codes=[6, 3, 5, 6, 3, 1], width=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.