StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POMost efficient algorithm for determining if X out of N inputs are true
text
Body
copied!<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 >= X) // true </code></pre> <hr> <p>What is a more efficient solution than either of these?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload