Task
You have an array of positive integers. Your task is to find an integer
x
such that the following are true:
- Bitwise AND between
x
and each array element is non-zero.- Number of ones in the binary expression of
x
is minimum.- If there are many such
x
, you should find smallest of them.Input Format
The first line contains a single integer
n
, the number of elements in the array. The second line containsn
space-separated integers.Constraints
1<=
n
<=10,000array elements are in range
[1; 2^26)
Please find a full description of the problem here.
My Effort
- Count a number of binary
1's
for each number from1
to \$2^{26} - 1\$. - Sort each number from
1
to \$2^{26} - 1\$ by its number of binary1's
. Use a normalstd::sort()
. Unfortunately, the counting sort is not an option here as its space complexity is too high for Hackerrank environment. - Check each sorted number from the previous step against the array numbers. If its
AND
with all of them is not0
- we've found the answer.
This approach has a \$O(m \cdot \log(m) \cdot n)\$ time and \$O(m)\$ space complexity where m
- maximum value of an array element and n
- size of the array. So, it produces a timeout error for every test case. It produces the correct result, though - I ran it locally for a couple of test cases.
I've tried a \$O(m \cdot n)\$ time and \$O(2 \cdot m)\$ space complexity solution (using the counting sort) but it didn't work due to a segmentation fault. As stated before, there's a limit as to how much memory one can use for this problem and that one was exceeded.
Code
#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>
uint32_t solve(std::vector<uint32_t>& array) {
const uint32_t upperBoundValue = (1 << 26);
std::vector<uint32_t> candidateNumbers(upperBoundValue);
for (uint32_t i = 0; i < upperBoundValue; i++) {
candidateNumbers[i] = i;
}
// sort all possible x's by their binary 1's in ascending order
std::sort(candidateNumbers.begin(), candidateNumbers.end(), [](const auto& a, const auto& b) {
std::bitset<26> bitSet1(a);
std::bitset<26> bitSet2(b);
size_t count1 = bitSet1.count();
size_t count2 = bitSet2.count();
if (count1 < count2) {
return true;
} else if (count2 < count1) {
return false;
} else {
return a < b;
}
});
// exclude duplicates from the array to reduce its size
std::sort(array.begin(), array.end());
array.erase(unique(array.begin(), array.end()), array.end());
uint32_t candidateIndex;
for (candidateIndex = 0; candidateIndex < upperBoundValue; candidateIndex++) {
bool candidateFound = true;
for (uint32_t index = 0; index < array.size(); index++) {
if (!(candidateNumbers[candidateIndex] & array[index])) {
candidateFound = false;
break;
}
}
if (candidateFound) {
break;
}
}
return candidateNumbers[candidateIndex];
}
int main() {
//read an array size
uint32_t size;
std::cin >> size;
//save each value into the corresponding array position
std::vector<uint32_t> array(size);
for (auto& element : array) {
std::cin >> element;
}
uint32_t bestMask = solve(array);
std::cout << bestMask << "\n";
return 0;
}
Question
Is there a way to improve the time complexity of this solution without exceeding the space limitation? Should a completely different approach be used here?