What Is Maximum of Minimum of “Score” of Any Binary Array and of Its Difference Array?

Revision en1, by Zaoly, 2023-12-10 11:14:27

A binary array is an array where all elements are either $$$0$$$ or $$$1$$$.

For any binary array $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$, we can figure out the corresponding unique array $$$b_1, b_2, \ldots, b_n$$$ of length $$$n$$$ that satisfies $$$b_1 = a_1$$$ and $$$b_i = a_i \oplus a_{i - 1}$$$ for any $$$2 \le i \le n$$$, where $$$\oplus$$$ denotes XOR operation. Then count the number of $$$1$$$-s in array $$$a$$$, count the number of $$$1$$$-s in array $$$b$$$, and find the minimum of them as the “score” of array $$$a$$$.

For example, provided $$$a = [1, 0, 1, 1, 0, 0]$$$, then $$$b = [1, 1, 1, 0, 1, 0]$$$. The number of $$$1$$$-s in array $$$a$$$ is $$$3$$$, the number of $$$1$$$-s in array $$$b$$$ is $$$4$$$, and the minimum of them is $$$3$$$, so the “score” of array $$$a = [1, 0, 1, 1, 0, 0]$$$ is $$$3$$$.

For any given $$$n$$$, what is the maximum “score” of array $$$a$$$ among all possible arrays $$$a$$$? And how to construct a possible array $$$a$$$?

Tags binary, array, difference array, score, minimum, maximum, counting

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Zaoly 2023-12-10 11:14:27 976 Initial revision (published)