36791

59
+136  Q:

## Check if at least 2 out of 3 booleans is true

An interviewer recently asked me this question: given 3 boolean variables a, b, c, return true if at least 2 out of the 3 are true.

My solution follows:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
} else {
return false;
}
}

He said that this can be improved further, but I'm not sure how?

+366  A:

Rather than writing:

if (someExpression) {
return true;
} else {
return false;
}

Write:

return someExpression;

As for the expression itself, something like this:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
return a ? (b || c) : (b && c);
}

or this (whichever you find easier to grasp):

boolean atLeastTwo(boolean a, boolean b, boolean c) {
return a && (b || c)
|| (b && c);
}

It tests a and b exactly once, and c at most once.

### References

+1: lovely solution to the puzzle, but hopefully we don't see anything like this in the real world :)
I love how every other answer is trying to optimize, while that's obviously not what the interviewer wanted to hear.
I don't think that looks *bad*, but if the requirement in the domain is understood to be "at least two", I think it'd be easier to read `atLeastTwo(hasgoodAttendance, passedCoursework, passedExam)`. The idea of "at least 2 bools are true" is generic enough to deserve its own function.
Jorn: can you elaborate? I would think that basic optimization is something that most programmers do instinctively. If you're trying to solve a problem, you're naturally going to go for the optimal route. Additionally, the poster wrote that the interviewer noted that his answer could be improved. And if you're being interviewed for a job, then you'd want your answer to be better than the other applicants'. Shooting for "just good enough" usually _isn't_ good enough.
@Lese: Asking the most micro-optimized code in face to face interviews is impractical, and dare I say, useless. Micro-optimizations, when driven by the need, is guided by runtime profiling results, not human instincts (which are known to be terrible). You can certainly ask interviewees the process by which you'd optimize this further; that's more important than the result itself.
@poly thumbs up... +1 cheers...
I don't agree with Juliet--it's a creative solution but I normally wouldn't answer such a thing with code I wouldn't want to see in the real world.
The ternary operator is a common idiom that you should be able to read. If you can't read it you should study it until you can. Use of the ternary operator is not something I consider "clever" in the derogatory sense.But yes, I'd put this as the body of a method call if you're commonly using the "at least two" logic.
In real-world situations, I'm a sucker for readability. I would actually use the function "isAtLeastTwo(e1,e2,e3)" instead of directly using ?: in the code.
So elegant. I must admire the beauty for a while longer. I will sit here and bask in it until my boss comes by.
Although, the question specifies two booleans must be true. If I'm reading this correctly, it will return true if at least two of these are false as well, correct?
@MattC: No. You're not reading it correctly. But imagine that it did return true in both scenarios: what would that be equivalent to?
That code tests b exactly once too?
@noelmarkham - yes, `b` is tested exactly once!
+90  A:

Why not implement it literally? :)

(a?1:0)+(b?1:0)+(c?1:0) >= 2

In C you could just write a+b+c >= 2 (or !!a+!!b+!!c >= 2 to be very safe).

In response to TofuBeer's comparison of java bytecode, here is a simple performance test:

class Main
{
static boolean majorityDEAD(boolean a,boolean b,boolean c)
{
return a;
}

static boolean majority1(boolean a,boolean b,boolean c)
{
return a&&b || b&&c || a&&c;
}

static boolean majority2(boolean a,boolean b,boolean c)
{
return a ? b||c : b&&c;
}

static boolean majority3(boolean a,boolean b,boolean c)
{
return a&b | b&c | c&a;
}

static boolean majority4(boolean a,boolean b,boolean c)
{
return (a?1:0)+(b?1:0)+(c?1:0) >= 2;
}

static int loop1(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority1(data[i], data[j], data[k])?1:0;
sum += majority1(data[i], data[k], data[j])?1:0;
sum += majority1(data[j], data[k], data[i])?1:0;
sum += majority1(data[j], data[i], data[k])?1:0;
sum += majority1(data[k], data[i], data[j])?1:0;
sum += majority1(data[k], data[j], data[i])?1:0;
}
}
return sum;
}

static int loop2(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority2(data[i], data[j], data[k])?1:0;
sum += majority2(data[i], data[k], data[j])?1:0;
sum += majority2(data[j], data[k], data[i])?1:0;
sum += majority2(data[j], data[i], data[k])?1:0;
sum += majority2(data[k], data[i], data[j])?1:0;
sum += majority2(data[k], data[j], data[i])?1:0;
}
}
return sum;
}

static int loop3(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority3(data[i], data[j], data[k])?1:0;
sum += majority3(data[i], data[k], data[j])?1:0;
sum += majority3(data[j], data[k], data[i])?1:0;
sum += majority3(data[j], data[i], data[k])?1:0;
sum += majority3(data[k], data[i], data[j])?1:0;
sum += majority3(data[k], data[j], data[i])?1:0;
}
}
return sum;
}

static int loop4(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
sum += majority4(data[i], data[j], data[k])?1:0;
sum += majority4(data[i], data[k], data[j])?1:0;
sum += majority4(data[j], data[k], data[i])?1:0;
sum += majority4(data[j], data[i], data[k])?1:0;
sum += majority4(data[k], data[i], data[j])?1:0;
sum += majority4(data[k], data[j], data[i])?1:0;
}
}
return sum;
}

static int loopDEAD(boolean[] data, int i, int sz1, int sz2)
{
int sum = 0;
for(int j=i;j<i+sz1;j++)
{
for(int k=j;k<j+sz2;k++)
{
}
}
return sum;
}

static void work()
{
boolean [] data = new boolean [10000];
java.util.Random r = new java.util.Random(0);
for(int i=0;i<data.length;i++)
data[i] = r.nextInt(2) > 0;
int sz1 = 100;
int sz2 = 100;
int sum = 0;

t0 = System.currentTimeMillis();

for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop1(data, i, sz1, sz2);

t1 = System.currentTimeMillis();

for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop2(data, i, sz1, sz2);

t2 = System.currentTimeMillis();

for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop3(data, i, sz1, sz2);

t3 = System.currentTimeMillis();

for(int i=0;i<data.length-sz1-sz2;i++)
sum += loop4(data, i, sz1, sz2);

t4 = System.currentTimeMillis();

for(int i=0;i<data.length-sz1-sz2;i++)
sum += loopDEAD(data, i, sz1, sz2);

System.out.println("a&&b || b&&c || a&&c : " + (t1-t0) + " ms");
System.out.println("   a ? b||c : b&&c   : " + (t2-t1) + " ms");
System.out.println("   a&b | b&c | c&a   : " + (t3-t2) + " ms");
System.out.println("   a + b + c <= 2    : " + (t4-t3) + " ms");
System.out.println("sum: "+sum);
}

public static void main(String[] args) throws InterruptedException
{
while(true)
{
work();
}
}
}

This prints the following on my machine (running Ubuntu on Intel Core 2 + sun java 1.6.0_15-b03 with HotSpot Server VM (14.1-b02, mixed mode)):

First and second iterations:

a&&b || b&&c || a&&c : 1740 ms
a ? b||c : b&&c   : 1690 ms
a&b | b&c | c&a   : 835 ms
a + b + c <= 2    : 348 ms
sum: 1472612418

Later iterations:

a&&b || b&&c || a&&c : 1638 ms
a ? b||c : b&&c   : 1612 ms
a&b | b&c | c&a   : 779 ms
a + b + c <= 2    : 905 ms

I wonder, what could java VM do that degrades performance over time for (a + b + c <= 2) case.

And here is what happens if I run java with a -client VM switch:

a&&b || b&&c || a&&c : 4034 ms
a ? b||c : b&&c   : 2215 ms
a&b | b&c | c&a   : 1347 ms
a + b + c <= 2    : 6589 ms

Mystery...

And if I run it in GNU Java Interpreter, it gets almost 100 times slower, but the a&&b || b&&c || a&&c version wins then.

Results from Tofubeer with the latest code running OS X:

a&&b || b&&c || a&&c : 1358 ms
a ? b||c : b&&c   : 1187 ms
a&b | b&c | c&a   : 410 ms
a + b + c <= 2    : 602 ms
`a+b+c >= 2` : this doesn't work with negatives, right? You may have to do the `!!a` thing, I'm not sure.
<s>-1. You should never do that for C. You don't know what the value of true is (it could just as easily be -1).</s> Actually I guess C99 includes in its standard that true is defined as 1. But I still wouldn't do this.
Is that possible if your input is result of boolean operations? And is that possible for "bool" type in C++?
@Rotsor: Nobody said the input has to be the result of boolean operations. Even without negatives you're playing with fire, as if you define it as 2 your condition would have false positives. But I don't care about that as much as I dislike the idea of intermingling booleans into arithmetic. Your Java solution is clear in that it does not rely on nuanced conversions from boolean to an integer type.
unexpected... and happy to be wrong... updating my answer slightly
Actually, I didn't expect it too. I thought that straightforward ab|bc|ac would be unbeatable.
One more surprise to me! It seems that result depends not on the runtime environment, but on the compiler. If I compile with *javac.exe*, then I get results similar to what TofuBeer got.If I compile with Eclipse builder, then I get my results published earlier.
Be cautious with microbenchmarks: http://java.sun.com/docs/hotspot/HotSpotFAQ.html#benchmarking_simple
BalusC, thank you. I split the benchmark into several smaller methods for HotSpot convenience and now it seems to run equally fast with all compilers.
Obviously, these results suggest you should use the DEAD method.
What does the !! do? Does that NOT NOT, or basically true->false->true?
This has to be some of the most awful repetitive code I've ever seen. I don't think I could trust it's outcome whatever it may be...
@joshperry Can't use virtual methods in performance-critical places, sorry.I wonder why such a poor question attracted so much attention anyway... I almost doubled my rep. and got my first "Good Answer" badge for doing a useless benchmark. :)
@Anthony D: I'm not a C user, but I would guess it normalizes a boolean value to some standard definition of true/false. So `!5 == 0`, `!!5 == !(!5) == !(0) == 1`
@Rotsor: Hey, my highest score to date is for my answer to "What's your favorite programmer joke". All that hard work testing code on some of my answers, the brilliant insights from years of experience, and my best score comes from a joke.
a + b + c <= 2 can be improved even further to (a + b + c) >> 1
+6  A:

The most obvious set of improvements are:

// no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}

return false;
}

and then

// no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
return ((a && b) || (b && c) || (a && c));
}

But those improvements are minor.

+24  A:

You don't need to use the short circuiting forms of the operators.

return (a & b) | (b & c) | (c & a);

This performs the same number of logic operations as your version, however is completely branchless.

Why would you want to force 5 evaluations when 1 could do? It really doesn't perform the same number of logic operations in truth. In fact, it would **always** perform more.
I think mixing binary arithmetic and boolean arithmetic is a bad idea. It is like driving screws in the wall with a wrench. Worst of all is they have different semantics.
@Mark - it might be faster ... depending on the effect of an incorrect branch prediction on the CPU pipeline. However, it is best to leave such micro-optimizations to the JIT compiler.
@Stephen C: OK, I see where he's coming from now but agree that's not something you should be doing explicitly in Java. Unfortunately I apparently can't remove my down-vote unless he edits it.
It is fine to do something like this in Java (or any other language)... with a couple of caveats: 1) it needs to be faster (in this case, I believe it is, see my second answer) 2) preferable significantly faster (not sure if it is), 3) most importantly documented since it is "odd". As long as it serves a purpose and it is documented it is fine to "break the rules" when it makes sense.
@Peter Tillemans There is no mixing with binary operators, in Java these are boolean operators.
+62  A:

Readability should be the goal. Someone who reads the code must understand your intent immediatelly. So here is my solution.

int howManyBooleansAreTrue =
(a ? 1 : 0)
+ (b ? 1 : 0)
+ (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;
Hmm, now I need a "two out of FOUR booleans" version... danatel's version is *much* easier now.
Or in Scala: `Seq(true, true, false).map(if (_) 1 else 0).sum >= 2`
@retronym: Hmm, no. The Java way works just fine in Scala and is both more readable and more efficient.
+67  A:

This kind of questions can be solved with a Karnaugh Map:

| C | !C
------|---|----
A  B | 1 | 1
A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

from which you infer that you need a group for first row and two groups for first column, obtaining the optimal solution of polygenelubricants:

(C && (A || B)) || (A && B)  <---- first row
^
|
first column without third case
@Justin, The Karnaugh map reduced the number of logical operations from 3 ANDs and 2 ORs to 2 ANDs and 2 ORs. @Jack, Thanks for reminding me of the Karnaugh Map's existence.
-1 for Karnaugh Maps and the poor readability they produce.
+1 for something new. My next functional spec will include a K-map, whether it needs it or it.
+39  A:

That's a trick question. It's obviously not a question about programming ability, because the answer is trivial. Whenever you see a question that simple, then the interviewer is really trying to assess your coding style.

Do you code for readability, with sensible data types and sensible structure? Or do you optimize the heck out of two lines of C code using bitwise operations and numerical conversions?

You know the correct answer, and you know the other answer. Now you have to asses which answer the interviewer wants. Does he think bit-hacks are neat tricks and demonstrate coding prowess? Or does he seem concerned about maintaining a large code base for an extended period of time?

A good interviewer does not care so much about a particular answer, but wants to know the process you use to come up with an answer.
Just ask him - "I know two solutions, a fast one and a very readable one. Which one do you want?" And you learn more from his answer than he from yours :-).
asses --> assess ;)
Remember as well that unless you are doing some specialist stuff, the readable solution will be more than fast enough execution time but will be much better development time when someone else has to work out what is going on...
+9  A:

Taking the answers (so far) here:

public class X
{
static boolean a(final boolean a, final boolean b, final boolean c)
{
return ((a && b) || (b && c) || (a && c));
}

static boolean b(final boolean a, final boolean b, final boolean c)
{
return a ? (b || c) : (b && c);
}

static boolean c(final boolean a, final boolean b, final boolean c)
{
return ((a & b) | (b & c) | (c & a));
}

static boolean d(final boolean a, final boolean b, final boolean c)
{
return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
}
}

and running them through the decompiler (javap -c X > results.txt):

Compiled from "X.java"
public class X extends java.lang.Object{
public X();
Code:
1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
4:   return

static boolean a(boolean, boolean, boolean);
Code:
1:   ifeq    8
5:   ifne    24
9:   ifeq    16
13:  ifne    24
17:  ifeq    28
21:  ifeq    28
24:  iconst_1
25:  goto    29
28:  iconst_0
29:  ireturn

static boolean b(boolean, boolean, boolean);
Code:
1:   ifeq    20
5:   ifne    12
9:   ifeq    16
12:  iconst_1
13:  goto    33
16:  iconst_0
17:  goto    33
21:  ifeq    32
25:  ifeq    32
28:  iconst_1
29:  goto    33
32:  iconst_0
33:  ireturn

static boolean c(boolean, boolean, boolean);
Code:
2:   iand
5:   iand
6:   ior
9:   iand
10:  ior
11:  ireturn

static boolean d(boolean, boolean, boolean);
Code:
1:   ifeq    8
4:   iconst_1
5:   goto    9
8:   iconst_0
10:  ifeq    17
13:  iconst_1
14:  goto    18
17:  iconst_0
20:  ifeq    27
23:  iconst_1
24:  goto    28
27:  iconst_0
29:  iconst_2
30:  if_icmplt   37
33:  iconst_1
34:  goto    38
37:  iconst_0
38:  ireturn
}

You can see that the ?: ones are slightly better then the fixed up version of your original. The one that is the best is the one that avoids branching altogether. That is good from the point of view of fewer instructions (in most cases) and better for branch prediction parts of the CPU, since a wrong guess in the branch prediction can cause CPU stalling.

I'd say the most efficient one is the one from moonshadow overall. It uses the fewest instructions on average and reduces the chance for pipeline stalls in the CPU.

To be 100% sure you would need to find out the cost (in CPU cycles) for each instruction, which, unfortunately isn't readily available (you would have to look at the source for hotspot and then the CPU vendors specs for the time taken for each generated instruction).

See the updated answer by Rotsor for a runtime analysis of the code.

Too many branches. Bad for the pipeline :(
+11  A:
boolean atLeastTwo(boolean a, boolean b, boolean c)
{
return ((a && b) || (b && c) || (a && c));
}
+11  A:

Another example of direct code:

int  n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);

It's not the most succinct code, obviously.

+1 @Loadmaster, I'm sorry but you're wrong! This is the most succinct answer here. (i.e. briefly AND clearly expressed) ;)
+11  A:

Here's a test-driven, general approach. Not as "efficient" as most of the solutions so far offered, but clear, tested, working, and generalized.

public class CountBooleansTest extends TestCase {
public void testThreeFalse() throws Exception {
assertFalse(atLeastTwoOutOfThree(false, false, false));
}

public void testThreeTrue() throws Exception {
assertTrue(atLeastTwoOutOfThree(true, true, true));
}

public void testOnes() throws Exception {
assertFalse(atLeastTwoOutOfThree(true, false, false));
assertFalse(atLeastTwoOutOfThree(false, true, false));
assertFalse(atLeastTwoOutOfThree(false, false, true));
}

public void testTwos() throws Exception {
assertTrue(atLeastTwoOutOfThree(false, true, true));
assertTrue(atLeastTwoOutOfThree(true, false, true));
assertTrue(atLeastTwoOutOfThree(true, true, false));
}

private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
return countBooleans(b, c, d) >= 2;
}

private static int countBooleans(boolean... bs) {
int count = 0;
for (boolean b : bs)
if (b)
count++;
return count;
}
}
Wow, I've never seen a **fully** tested method before seeing this one.
I personally find this code awful, for so many reasons. I'm not going to downvote, but if I ever saw this in production code I would curse. An extremely simple boolean operation does not need to be complicated like this.
I'd be very interested to know your reasons, @CaptainCasey. I think this is pretty good code. There's a nice generalized function that's easy to understand, easy to verify, and a specific function that takes advantage of it, also easy to understand other than that - I'd happily put this code into production. Oh - yeah - I'd rename countBooleans() to countTrue().
@Carl - your code is spending a lot of time creating temporary boolean arrays. Very strange for profiling performance.
Can't... tell... satire... or serious... aaargh...
@Carl: I'd say that this code is overgeneralized. Most of the single-method solutions from other answers are equally easy to understand and verify. So unless you have another use for `countBooleans` elsewhere in your code there's no reason to have two methods where one does fine.
if its not about performance, this solution looks nearly perfect for me: very easy to read and extendable. Thats exactly what var-args are made for.
TDD FTW huh? ^^
@Krougan I was certain it was a joke until I saw his comment; now I'm not sure
@Michael, @Krougan: Not a joke. I am well aware that my solution isn't as performant as the others; I think it's clearer and more general, and I think that has value. You're entitled to your contrary opinion, of course.
I sort of admire the sheer psychotic religious doggedness of this, but please just shoot me if I *ever* write code like it. (And no, performance is not the issue.)
@walkytalky I'd rather exercise psychotic religious doggedness with respect to correctness, clarity, and generality than to clipping off that one last machine instruction; I think there is much greater value in that, with today's platforms. YMMV.
@Carl Was my final sentence somehow unclear? I couldn't care less about that last machine instruction. Writing half a page of scripture in place of a simple expression is not clarity at all, it is obfuscation. And if the only way you can think of to demonstrate correctness is absolute exhaustion then how do you ever get anything done?
@walkytalky Your final sentence was somewhat obscured by the insult of your first. As it happens, I had the complete working solution written after test #2; I added the remaining tests so readers would have no doubt of the correctness. It took about 30 seconds and I don't consider the time wasted.
@Carl I certainly apologise for the insult - the sentence was intended lightheartedly, but reads as rude - sorry for that. On the rest we must agree to disagree.
@walkytalky Apology accepted; we're cool.
+10  A:

Here's another implementation using map/reduce. This scales well to billions of booleans© in a distributed environment. Using MongoDB:

Creating a database values of booleans:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

Creating the map, reduce functions:

Edit: I like CurtainDog's answer about having map/reduce apply to generic lists, so here goes a map function which takes a callback that determines whether a value should be counted or not.

var mapper = function(shouldInclude) {
return function() {
emit(null, shouldInclude(this) ? 1 : 0);
};
}

var reducer = function(key, values) {
var sum = 0;
for(var i = 0; i < values.length; i++) {
sum += values[i];
}
return sum;
}

Running map/reduce:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false

function isTrue(object) {
return object.value == true;
}

function containsMinimum(count, resultDoc) {
var record = db[resultDoc].find().next();
return record.value >= count;
}
yeah, by me ...
@Andrew - nah that costs money, copyright is easy
+5  A:

Yet another way to do this but not a very good one:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

The Boolean hashcode values are fixed at 1231 for true and 1237 for false so could equally have used <= 3699

or (a?1:0)+(b?1:0)+(c?1:0) >= 2
+1 for awesome obfuscation.
+2  A:

The simplest way (imo) that is not confusing and easy to read:

// three booleans, check if 2+ are true

return ( a && ( b || c ) ) || ( b && c );

How is this different to the accepted answer?
Functionally, it is the same. Syntactically, it makes it easier to read for those unaccustomed to the use of the question mark conditional operator. I am willing to bet more people know how to use AND and OR operators than the number of people who know how to use question mark conditional operators.The original question asks for an "improved answer".. The accepted answer does simplify the answer, but raises a very interesting question of what does one consider improvement. Do you program for universal readability or for simplicity?To me, this is an improvement over the accepted answer :)
@abelito: Personal preferences. For me it's way more easy to understand the cleaner ternary operator than this solution.
Ah yeah, I saw this problem and was wondering why no one else mentioned this solution.If you write out the OP's logic as boolean algebra, you get A*B+A*C+B*C, which has five operations. By the associative property, you can write A*(B+C)+B*C, which has four operations.
A:

Ternary operators get the nerd juices flowing, but they can be confusing (making code less maintainable, thus increasing the potential for bug injection). Jeff Attwood said it well here:

It's a perfect example of trading off an utterly meaningless one time write-time savings against dozens of read-time comprehension penalties-- It Makes Me Think.

Avoiding ternary operators, I've created the following function:

function atLeastTwoTrue(\$a, \$b, \$c) {
\$count = 0;

if (\$a) { \$count++; }
if (\$b) { \$count++; }
if (\$c) { \$count++; }

if (\$count >= 2) {
return true;
} else {
return false;
}
}

Is this as cool as some of the other solutions? No. Is it easier to understand? Yes. Will that lead to more maintainable, less buggy code? Yes.

Why not simply `return (\$count >= 2);`? Also it's a duplicate of this answer - http://stackoverflow.com/questions/3076078/check-if-at-least-2-out-of-3-booleans-is-true/3076954#3076954
@ChrisFThe if () {return bool} is more clear to me. I can see how some think it is too verbose.My solution is very similar to http://stackoverflow.com/questions/3076078/check-if-at-least-2-out-of-3-booleans-is-true/3076954#3076954 but it is more complete and contains some justification (the text about ternary operators being confusing).
Personally I find multiple if statements Make Me Think more than ternary operators, since each if statement represents a different possible execution path. A single line, OTOH, will always set the value to the left of the equals sign exactly once, no matter how many ternary operators are used to the right of the equals sign.
I much prefer Ternary operators to multi-line stuff that I replace. I often (in legacy code) take ~10 lines down to one with a ternary. Less text = more code on screen = more context.
Yeah man... it isn't *just* about being cool. Ternaries are *shorter*. Less to read, less to comprehend. Unless you *really* struggle with them, one little ternary is a lot quicker to understand than the... 8 lines and branching opportunities you have there.
+3  A:
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
return (System.Convert.ToInt16(val1) +
System.Convert.ToInt16(val2) +
System.Convert.ToInt16(val3)) > 1;
}

Too many ways to do this...

Look more like C#. This should be mentioned as such in the answer since the question is Java-targeted :)
Yuck. ---------
+5  A:

I don't like ternary (return a ? (b || c) : (b && c); from the top answer) and I don't think I've seen anyone mention it written like this so

boolean atLeastTwo(boolean a, boolean b, boolean c) {
if (a) {
return b||c;
} else {
return b&&C;
}
yes it should, thanks, copyandpastelaziness--
+143  A:

Just for the sake of using XOR to answer a relatively straight-forward problem...

return a ^ b ? c : a
Wow, cool solution.But for me its inverted version is easier to understand: a==b ? a : c
Yeah, that's definitely more clear for anyone who has to read the code. Heh, admittedly I'd probably do a quick double-take at what I wrote if I saw it somewhere else.
a ^ b ? c : a ^ b ? c : a ^ b ? c : a
i love this one better than the accepted answer.
Yay,..XOR gets such a bad press and you seldom get the chance to use it.
@Stimul8d maybe because, for booleans, it's the same as != but less readable? Figuring that out was a eureka moment for me...
A:
function atLeastTwoTrue(\$a, \$b, \$c) {

int count = 0;
count = (a ? count + 1 : count);
count = (b ? count + 1 : count);
count = (c ? count + 1 : count);
return (count >= 2);
}
Gahh... why?! The other counting methods already posted are so much better!
+2  A:

A C solution.

int two(int a, int b, int c) {
return !a + !b + !c < 2;
}

or you may prefer:

int two(int a, int b, int c) {
return !!a + !!b + !!c >= 2;
}
+5  A:

Why restrict it to 3 booleans?

(define (_true? args #!optional (flag #f))
(if (null? args)
flag
(if (car args)
(if flag
#t
(true? (cdr args) (or flag (car args))))
(_true? (cdr args) flag))))

(define (true? . args)
(_true? args))

(true? #t #t #f)

I know this isn't Java. Just playing around...

+4  A:

If the non-functional requirements are more readability than performance, one way is:

public int Count(params bool[] conditions)
{
return conditions.Count(a => a);
}

public bool AtLeast(int n, params bool[] conditions)
{
return Count(conditions) >= n;
}

public bool AtLeastTwo(bool a, bool b, bool c)
{
return AtLeast(2, a, b, c);
}
+1. This was my first thought. Clear and easily usable for any 'X out of Y are true' situation.
Didn't see the Java part of the question, but you get the idea... :)
+1  A:
return 1 << \$a << \$b << \$c >= 1 << 2;
Didn't see Suvega's answer before posing this, pretty much the same thing.
Does this really work? I assume this is PHP, but I don't have access to it, but I'll just ask you: what happens if \$a is 0?
@Mark It actually doesn't work if \$a is 0. That was an oversight. Thanks for pointing that out. :)
+11  A:

Sum it up. It's called boolean algebra for a reason:

0 x 0 = 0
1 x 0 = 0
1 x 1 = 1

0 + 0 = 0
1 + 0 = 1
1 + 1 = 0 (+ carry)

If you look at the truth tables there, you can see that multiplication is boolean and, and simply addition is xor.

return (a + b + c) >= 2
This is the most elegant solution, in my opinion.
Rookie mistake though, a boolean value is NOT 0, that does not mean its always 1.
Except that the tag on the post says "Java", and you can't write "a+b+c" when they are defined as booleans in Java.
A:

My first thought was

return (a||b)&&(b||c)

but for ease of reading I liked the proposed a+b+c>=2 solution that you guys suggested better

Your answer returns an incorrect value when a and c are false, and only b is true.
A:

Definitely a question that's more about how you solve problems/think than your actual coding ability.

A slightly terser version could be

return ((a ^ b) && (b ^ c)) ^ b

But like a previous poster said, if I saw this in any code I was working on, someone would be getting an earful. :)

A:

literal interpretation will work in all major languages

return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;

but I would probably make it easier for people to read, and expandable to more than 3 - something that seems to be forgotten by many programmers

boolean testBooleans(Array bools)
{
int minTrue = ceil(bools.length * .5);
int trueCount = 0;

for(int i = 0; i < bools.length; i++)
{
if(bools[i])
{
trueCount++;
}
}

return trueCount >= minTrue;
}
+3  A:

I don't think I've seen this solution yet:

boolean atLeast(int howMany, boolean[] boolValues) {
// check params for valid values

int counter = 0;
for (boolean b : boolValues) {
if (b) {
counter++;

if (counter == howMany) {
return true;
}
}
}
return false;
}

Its advantage is that once it reaches the number that you're looking for, it breaks. So if this was "at least 2 out of this 1,000,000 values are true" where the first two are actually true, then it should go faster than some of the more "normal" solutions.

That should probably be:if (++counter == howMany)instead of incrementing and then checking separately.
I'd do `boolean ... boolValues` so it's easier to call, but still takes an array
I'm not up to date on my Java - didn't know that existed. Kind of a strange syntax, but it's useful - every once in a while I'll do that in C# (params keyword), and it does make things nicer to call. Or, I don't know about Java, but in .NET, arrays and all collections implement IEnumerable<T>, so I'd probably use whatever Java's equivalent is.
How does the performance of this compare against the 2of3 example? return a ? (b || c) : (b
+3  A:

clojure:

(defn at-least [n & bools]
(>= (count (filter true? bools)) n)

usage:

(at-least 2 true false true)
+1 Great generic version shows the power of the Lisps. Thanks,
A:

X = OR(a+b,c)

a b c X

1 1 0 1

0 0 1 1

0 1 1 1

A:

If the goal is to return a bitwise two-out-of-three value for three operands, arithmetic and iterative approaches are apt to be relatively ineffective. On many CPU architectures, a good form would be "return ((a | b) & c) | (a & b);". That takes four boolean operations. On single-accumulator machines (common in small embedded systems) that's apt to take a total of seven instructions per byte. The form "return (a & b) | (a & c) | (b & c);" is perhaps nicer looking, but it would require five boolean operations, or nine instructions per byte on a single-accumulator machine.

Incidentally, in CMOS logic, computing "not two out of three" requires twelve transistors (for comparison, an inverter requires two, a two-input NAND or NOR requires four, and a three-input NAND or NOR requires six).

A:

Objective Caml version:

let at_least_two = function
| (true, true, _)
| (true, _, true)
| (_, true, true) -> true
| _ -> false
;;

For people who are curious about Objective Caml, these pipe operators are a pattern match; they're like switch statements on steroids. The underscores mean "match anything", and that final clause is like a default: case.

It's functionally identical to:

let at_least_two (a, b, c) =
if a && b then
true
else if a && c then
true
else if b && c then
true
else
false
;;

With some practice, I find the OCaml pattern match syntax both more succinct and clearer at representing the problem being solved than any of the other solutions. Of course, this isn't immediately true for other programmers since most programmers are much more familiar with Java than some obscure academic language like OCaml. :)

Examples of the function being called at a REPL:

# at_least_two (true, false, false) ;;
- : bool = false
# at_least_two (false, false, false) ;;
- : bool = false
# at_least_two (true, false, true) ;;
- : bool = true
A:

I believe using plain boolean operators (a || b) && (b || c) is fine and is simpler.

You can swap any of the 3 letters with any of the other two and it's still the same expresion.

except this answer is wrong. it would return true if only b is true
You're right. So I stick to a+b+c>=2 then. Works for PHP and Python too.
A:

One thing I haven't seen others point out is that a standard thing to do in the "please write me some code" section of the job interview is to say "Could you improve that?" or "Are you completely happy with that" or "is that as optimized as possible?" when you say you are done. It's possible you heard "how would you improve that" as "this might be improved; how?". In this case changing the if(x) return true; else return false; idiom to just return x is an improvement - but be aware that there are times they just want to see how you react to the question. I have heard that some interviewers will insist there is a flaw in perfect code just to see how you cope with it.

A:

Clearly, the right way is to use C++ templates. That way, you can compute the answer in compile time - this is surely what your employer had in mind.

template<bool A, bool B>
struct TwoEqual
{
static const bool value = A == B;
};

template<bool A, bool B, bool C>
struct AtLeastTwo
{
static const bool value = TwoEqual<A, B>::value || TwoEqual<B, C>::value || TwoEqual<A, C>::value;
};

You can then do something like

cout << AtLeastTwo<true, false, false>::value << endl;
I doubt that's what the interviewer meant. He used the term 'variables' which implies l-values. Also even using templates, you don't need the TwoEqual template. It's easiest enough to write:static const bool value = A ? (B || C): (B
+22  A:

The CORRECT answer, and the only one that I accept from the programmers I interview is:

improved by what metric?

I do not want to see a "process" or the variety of answers available. I want to know that he or she can ask for more details when problems are ambiguous and can take direction. THAT is the test.

+1. Most people answering this question have utterly missed the point and can't resist the need to just show how "clever" they are.
A:

if (a) {
return b || c;
} else {
return b && c;
}
A:

Here's a list comprehension solution in Erlang:

at_least_two(BoolList) ->
length( [X || X <- BoolList, X] ) >= 2;

Or more generically:

at_least(N, BoolList) ->
length( [X || X <- BoolList, X] ) >= N;
A:

The best answer to the question should be "As an employee, it's important I write it so that my meaning is clear while maintaining efficiency where necessary for performance." Here's how I'd write it:

function atLeastTwoAreTrue(a, b, c) {
return (a && b) || (b && c) || (a && c);
}

In reality, the test is so contrived that writing a method that's the fastest, most cryptic possible is perfect acceptable if you accomodate it with a simple comment. But, in general, in this one-liner world, we need more readable code in this world. :-)

A:

Calculated via truth table.

return (A and B) or (c and (a ^ b))

The ^ symbol is the xor operator.

Well, the original solution is easier.
+8  A:
(a==b) ? a : c;
c is never even tested... brilliant!
A:

FYI, this is just the carry-out bit of a full adder. In hardware, you could use the logical effort to determine the optimal circuit based on the different boolean expressions. I would guess that the traditional XOR solution would take more effort than the less succinct expression that the poster presented.

+1  A:

I know you tagged this as Java, but I'll give you a nudge towards Scala anyway, you can make this much nicer :)

First of all add an automatic way to transform a boolean into a number:

implicit def bool2num(a:Boolean) = if (a) 1 else 0

Now the solution becomes trivial:

def atLeast2(a:Boolean,b:Boolean, c:Boolean) = a + b + c >= 2

But why stop at testing 2 out of 3? It's even easier to make something generic:

def atLeastN(l:List[Boolean], n:Int) = l.foldLeft(0)(_+_)>=n

But for that you don't even need the conversion to a number:

def atLeastN(l:List[Boolean], n:Int) = l.count(a=>a)>=n

Typesafe and elegant ;)

A:

Python:

def at_least(things, count):
return len(filter(lambda x: bool(x), things)) >= count

at_least([True, False, True], 2)

Has the nice benefit to work on iterables of arbitrary length.

A:

Not Java, but here are a couple different approaches in scheme.

Not the most efficient thing in the world, but it's functionally correct and far more flexible.

(define (count-true . vals)
(apply + (map #L(if _ 1 0) vals)))

(define (n-majority? n . vals)
(>= (apply count-true vals) n))

(define (2-majority? . vals)
(apply n-majority? 2 vals))

Another stricter implementation, using a sum.

(define (2-majority? v0 v1 v2)
(define (->0/1 bool) (if bool 1 0))
(>= (+ (->0/1 v0)
(->0/1 v1)
(->0/1 v2))
2))

And a transliteration of the ternary expression in the highest rated answer (which is my favorite Java solution, particularly if it had a nice comment or was wrapped in a function with a descriptive name):

(define (2-majority? v0 v1 v2)
(if v0
(or v1 v2)
(and v1 v2)))

And here's a macro that should produce majority expressions at will. (n is the number of trues you need.)

(defmacro (n-majority? n . vs)
(cond ((> n (length vs)) #f)
((= n 0)           #t)
(#t
`(if ,(car vs)
`(n-majority? ,(- n 1) ,@(cdr vs))
`(n-majority? ,n ,@(cdr vs))))))

This last solution gives you both compile-time flexiblity and speed. I'm also pretty sure that it guarantees that no expression in vs is evaluated more than once (which is quite useful). The aspect of it that still needs improvement (besides much more testing) is that it needs better error handling.

A:

c#

off of the top of my head:

public bool lol( int minTrue, params bool[] bools )
{
return bools.Count( ( b ) => b ) >= minTrue;
}

should be pretty quick.

A call would look like this:

lol( 2, true, true, false );

This way you are leaving the rules (two must be true) up to the caller, instead of embedding them in the method.

A:

static boolean five(final boolean a, final boolean b, final boolean c)
{
return a == b ? a : c;
}

Consider also it's disassembled version as given by "javap -c"

static boolean five(boolean, boolean, boolean);
Code:
2:   if_icmpne   9
6:   goto    10
10:  ireturn

pdox's answer compiles to less byte code than any of the previous answers. How does its execution time compare to the others?

one                5242 ms
two                6318 ms
four               7192 ms
five  (pdox)       3650 ms

At least on my computer pdox's answer is just slightly faster than moonshadow's answer, making pdox's the fastest overall (at least on my HP/intel laptop).

+3  A:

It really depends what you mean by "improved":

Clearer?

boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
return (a && b) || (a && c) || (b && c);
}

Terser?

boolean moreThanTwo(boolean a, boolean b, boolean c)
{
return a == b ? a : c;
}

More general?

boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;

for(boolean b : bs)
{
count += b ? 1 : 0;

if(count > x) return true;
}

return false;
}

More scalable?

boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;

for(int i < 0; i < bs.length; i++)
{
count += bs[i] ? 1 : 0;

if(count > x) return true;

int needed = x - count;
int remaining = bs.length - i;

if(needed >= remaining) return false;
}

return false;
}

Faster?

// Only profiling can answer this.

Which one is "improved" depends heavily on the situation.

A:
int count=0;

boolean atLeastTwo(boolean a, boolean b, boolean c) {

if (a)
count++;
if (b)
count++;
if (c)
count++;

if (count>1)
return true;
else
return false;
}
+1  A:

In Ruby:

[a, b, c].count { |x| x } >= 2

Which could be run in JRuby on the JavaVM. ;-)

+1  A:

The 2 and 3 in the question posed are decidedly magic-numberish. The 'correct' answer will depend on whether the interviewer was trying to get at your grasp of boolean logic (and I don't think pdox's answer could be bested in this respect) or your understanding of architectural issues.

I'd be inclined to go with a map-reduce solution that will accept any sort of list with any arbitrary condition.

A:

I found this solution.

boolean atLeastTwo(boolean a, boolean b, boolean c) {
bool result = !(a ^ b ^ c) && !(!a & !b & !c) || (a & b & c);
return result;
}
A:

My first thought when I saw the question was:

int count=0;
if (a) ++count;
if (b) ++count;
if (c) ++count;
return count>=2;

After seeing other posts, I admit that

return (a?1:0)+(b?1:0)+(c?1:0)>=2;

is much more elegant. I wonder what the relative runtimes are.

In any case, though, I think this sort of solution is much better than a solution of the

return a&b | b&c | a&c;

variety because is is more easily extensible. What if later we add a fourth variable that must be tested? What if the number of variables is determined at runtime, and we are passed an array of booleans of unknown size? A solution that depends on counting is much easier to extend than a solution that depends on listing every possible combination. Also, when listing all possible combinations, I suspect that it is much easier to make a mistake. Like try writing the code for "any 3 of 4" and make sure you neither miss any nor duplicate any. Now try it with "any 5 of 7".

You can push it further: I believe in C you could do return a+b+c>1;
Fififox: True, but the question is tagged "Java", where this would not work. The (a?1:0) solution is the closest Java equivalent to what you are suggesting for C. One could, I am sure, endlessly debate the relative merits. In C you can do easy shortcuts by treating booleans an ints; in Java you are protected from hurting yourself by accidentally treating booleans as ints.
A:

He's probably not looking for anything convoluted like bitwise comparison operators (not normally convoluted but with booleans, it's extremely odd to use bitwise operators) or something that is very roundabout like converting to int and summing them up.

The most direct and natural way to solve this is with an expression like this:

a ? (b || c): (b && c)

Put it in a function if you prefer, but it's not very complicated. The solution is logically concise and efficient.

A:

In C# the following LINQ query could be used:

bool atLeastTwo(bool a, bool b, bool c)
{
return (from v in new[] {a, b, c} where v select v).Count() >= 2;
}

It clearly expresses the intention and is scalable to any number of booleans.

It's nice to know you can do that but it has to do too much computation in order to come with such a simple result in the case of just three booleans. It starts to look interesting when you have a collection but then you are basically turning to a "reduce" approach, that is, iterating over the collection and using a counter.
A:
#include<stdio.h>

int two(int a, int b, int c){
return  (a+b+c)>>1;
}

int main(){
printf("%d %d %d %d\n",
two(0,0,0), two(0,0,1), two(0,1,1), two(1,1,1));
return 0;
}

Output: 0 0 1 1

this is much more complicated than it needs to be. let me guess, you are a windows developer?
Embedded C developer.
A:

Let the three boolean values be A,B and C....

You can use a k-MAP and come with a boolean expression ...

In this case boolean expression will be A(B+C) + C

or if((A && (B || C )) || C ) { return true; } else return false;

@Egalitarian: Doesn't this return true with just C been true?
oops ... i forgot to add something... its if((A } else return false;
A:

C:

if (!!a + !!b + !!c >= 2)
+2  A:

C'mon guys... Why nobody gave this:

(a || b && c) && (b || c && a)

Also, if true is automatically converted to 1 and false to 0:

(a + b*c) * (b + c*a) > 0