CODEWITHSUNDEEP
algorithmbit-manipulation
Madfish
Madfish

Reputation: 85

Number of pairs with given OR value

Is it possible to write a function that takes an array of n integers and an integer k and returns the number of pairs of array elements with BITWISE OR value equal to k in better than O(n2) time?

Example: If we have an array = [21, 10, 29, 8] and k = 31, then the function should return 2, since the valid pairs are (21, 10) and (10, 29).

* for clarity * 21 OR 10 = 31 , 21 OR 29 = 29 , 21 OR 8 = 29, 10 OR 29 = 31, 10 OR 8 = 10,29 OR 8 = 29, so answer is 2.

**** k is a constant which is always 31 .****

Upvotes: 4

Views: 477

Answers (2)

Eric Postpischil
Eric Postpischil

Reputation: 223633

Assuming the units of time are elementary operations on a word size that spans k, then O(n + k2) is possible:

#include <stdio.h>
#include <stdlib.h>

#define NumberOf(a) (sizeof (a) / sizeof *(a))


static unsigned Count(size_t N, unsigned *A, unsigned k)
{
    //  Count number of elements with each pattern of bits in k.
    unsigned *C = calloc(k + 1, sizeof *C);
    if (!C) exit(EXIT_FAILURE);
    for (size_t n = 0; n < N; ++n)
        if ((A[n] & ~k) == 0) ++C[A[n]];

    //  Count number of solutions formed with different values.
    unsigned T = 0;
    for (size_t i = 0; i < k; ++i)
    for (size_t j = i+1; j <= k; ++j)
        if ((i | j) == k)
            T += C[i] * C[j];

    //  Add solutions formed by same value (only possible when both are k).
    T += C[k] * (C[k]-1) / 2;

    free(C);

    return T;
}


int main(void)
{
    unsigned A[] = { 21, 10, 29, 8 };
    printf("%u\n", Count(NumberOf(A), A, 31));
}

This can be reduced to O(n + p2), where p is the number of bits set in k, by compressing each array element to just those bits (removing bits not in k and shifting the remaining bits to be contiguous). Also, the main loop that counts the combinations could be improved, but I do not think that affects the O() time.

Upvotes: 5

Reputation Farmer
Reputation Farmer

Reputation: 387

People believe that the answer is "NO".

Assume that your k is 2^s - 1 (so it's 111...111 in binary) and all numbers are of at most k. Then

a or b = k <=> (~a) and (~b) = 0.

, where ~ is a "bitwise not". E.g.

110 or 101 = 111 <=> 001 and 010 = 0

This is a general Orthogonal Vector Problem (OVP), and popular conjecture states that it's not solvable faster than O(n^2) (there are some details I omit).

See Conjecture 1 here: https://arxiv.org/pdf/1510.02824.pdf.

Upvotes: 1

Related Questions