Find positive integer with a minimum number of binary 1's such that its bitwise AND with all array elements is not 0

Question

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 contains n space-separated integers.

Constraints

• 1<=n<=10,000

• array 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 from 1 to \$2^{26} - 1\$.
• Sort each number from 1 to \$2^{26} - 1\$ by its number of binary 1's. Use a normal std::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 not 0 - 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?

Answer 1

Is there a way to improve the time complexity of this solution without exceeding the space limitation?

Yes, there's a way. We don't actually need any additional array of numbers because we can check all numbers from 1 to the maximum possible mask for given elements of the array. Then, we will perform AND of the current number candidate with all array elements only if its 1's count lower than that of the current best candidate. Please check the code for more details.

Should a completely different approach be used here?

I've come up with a similar brute force approach that requires only additional O(1) space. It's quite simple and also passes all the tests.

Remove duplicates from the original array

We can safely do it because duplicate elements do not influence the final answer. It also helps us to reduce the size of the array and thus improve the time complexity of the algorithm.

Sort the array by 1's count

By doing so, we won't perform a bitwise AND for most of best mask candidates with ALL array elements and thus save a lot of execution time.

Perform AND only for candidate numbers having fewer 1's

That's another important optimisation. Before checking a candidate against the array elements make sure it has fewer 1's than the current best candidate.

Code

#include <vector>
#include <iostream>
#include <algorithm>
#include <bitset>

uint8_t popCount(const uint32_t& number) {
    std::bitset<26> bitSet(number);

    return bitSet.count();
}

uint32_t solve(std::vector<uint32_t>& array) {
    // exclude duplicates from the array to reduce its size
    std::sort(array.begin(), array.end());
    array.erase(unique(array.begin(), array.end()), array.end());

    // sort array elements based on their 1's count in ascending order
    std::sort(array.begin(), array.end(), [](const auto& a, const auto& b) {
        uint8_t count1 = popCount(a);
        uint8_t count2 = popCount(b);

        if (count1 == count2) {
            return a < b;
        }
        return count1 < count2;
    });

    // Initially, bestMask is the maximum possible mask
    uint32_t maxPossibleMask = 0;
    for (const auto& element : array) {
        maxPossibleMask |= element;
    }

    uint32_t bestMask = maxPossibleMask;
    for (uint32_t bestMaskCandidate = 1; bestMaskCandidate < maxPossibleMask; bestMaskCandidate++) {
        if (popCount(bestMaskCandidate) < popCount(bestMask)) {

            bool candidateFound = true;
            for (uint32_t index = 0; index < array.size(); index++) {
                if (!(bestMaskCandidate & array[index])) {
                    candidateFound = false;
                    break;
                }
            }

            if (candidateFound) {
                bestMask = bestMaskCandidate;
            }
        }
    }

    return bestMask;
}

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;
}