title: Most efficient algorithm for determining if X out of N inputs are true
body: <p>This question was inspired by an answer I was working on yesterday. </p>
  
  <blockquote>
    <p>Let's say we have N inputs that evaluate to either true or false,
    what is the most efficient way to determine if X of those inputs are
    true? </p>
  </blockquote>
  
  <p><strong>Caveats:</strong></p>
  
  <blockquote>
    <ol>
    <li>The inputs are not in an array, so if you convert them to an array please account for any overhead costs.  </li>
    <li>By "most efficient" I mean in terms of best average case (although I would love to see best and worst case stats too).</li>
    </ol>
  </blockquote>
  
  <hr>
  
  <p>Here  are two of the methods I came across yesterday. </p>
  
  <p><strong>1) Think of the variables as Boolean inputs for a circuit and reduce them using a K-map</strong></p>
  
  <p>At first I thought this would be the most efficient means because it follows circuit logic, but I've definitely had second thoughts. As the number of inputs increases, the number of comparisons goes up exponentially</p>
  
  <pre><code>2 inputs:
     1 of 2: if(1 OR 2)
     2 of 2: if(1 AND 2)
  
  3 inputs:
     1 of 3: if(1 OR 2 OR 3)
     2 of 3: if((1 AND 2) OR (1 AND 3) OR (2 AND 3))
     3 of 3: if(1 AND 2 AND 3)
  
  4 inputs:
     1 of 4: if(1 OR 2 OR 3 OR 4)
     2 of 4: if((1 AND 2) OR (1 AND 3) OR (1 AND 4) OR (2 AND 3) OR (2 AND 4) OR (3 AND 4))
     3 of 4: if((1 AND 2 AND 3) OR (1 AND 2 AND 4) OR (1 AND 3 AND 4) OR (2 AND 3 AND 4))
     4 of 4: if(1 AND 2 AND 3 AND 4)
  
  ... etc. ...
  </code></pre>
  
  <p>The best case scenario is fine (<code>O(1)</code>), but the worst case is far worse than...</p>
  
  <p><strong>2) A counter and sequential if statements</strong></p>
  
  <p>This performs in <code>O(n)</code> time always, which is OK, but I was hoping for a better best case.</p>
  
  <pre><code>counter = 0
  
  if(input 1)
     counter++
  
  if(input 2)
     counter++
  
  if(input 3)
     counter++
  
  ... etc. ...
  
  if(counter &gt;= X)
     // true
  </code></pre>
  
  <hr>
  
  <p>What is a more efficient solution than either of these?</p>