<p>People believe that the answer is "NO".</p>

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

<pre><code>a or b = k &lt;=&gt; (~a) and (~b) = 0.
</code></pre>

<p>, where <code>~</code> is a "bitwise not". E.g.</p>

<pre><code>110 or 101 = 111 &lt;=&gt; 001 and 010 = 0
</code></pre>

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

<p>See Conjecture 1 here: <a href="https://arxiv.org/pdf/1510.02824.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1510.02824.pdf</a>.</p>
Number of pairs with given OR value
<p>Is it possible to write a function that takes an array of <em>n</em> integers and an integer <em>k</em> and returns the number of pairs of array elements with BITWISE OR value equal to <em>k</em> in better than O(<em>n</em><sup>2</sup>) time?</p>

<p>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).</p>

<p><strong>* for clarity *</strong>
 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.</p>

<p>**** k is a constant which is always 31 .****</p>