Finding N bits using O(N/logN) sums


binary array
query problem
divide et impera

How to Cite

Corlat, S., Guzun, V., & Vorona, V. (2023). Finding N bits using O(N/logN) sums. Acta Et Commentationes Exact and Natural Sciences, 14(2), 101-105.


The problem we are trying to solve sounds as follows: You are given $N$ bits. Find the value of each bit. We will show a technique which enables finding the values of $N$ bits using $O(\frac{N}{\log N})$ subsequence-sum queries. The algorithm consists of two phases: Constructing the queries for each layer and using the queries for a particular layer to get the value of every bit. We described the following technique in this blog [1], which was inspired by this article [2]. It should be noted that this number of queries is indeed the optimal one for finding all $N$ bits of a binary array, since each subsequence-sum queries offers us at most $\log_{2} N$ bits of information.
Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.