Reputation: 3165

Check if at least two out of three booleans are true

An interviewer recently asked me this question: given three boolean variables, a, b, and c, return true if at least two out of the three 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 how?

Upvotes: 615

Answers (30)

user1883212

Reputation: 7859

I think the simplest solution is:

return (a && b) || c;

Upvotes: -7

labratmatt

Reputation: 1841

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++; }

    return $count >= 2;
}

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.

Upvotes: 2

Dupinder Singh

Reputation: 7769

This is very simple with the help of arithmetic operation.

boolean a = true;
boolean b = false;
boolean c = true;

// Exactly one boolean value true.
return (a?1:0)+(b?1:0)+(c?1:0)==1;

// Exactly 2 boolean value true.
return (a?1:0)+(b?1:0)+(c?1:0)==2;

And this is how you can just increase the value of constant to check how many boolean values are true.

Upvotes: 0

Dhananjay

Reputation: 3793

Function ko returns the answer:

static int ho(bool a)
{
    return a ? 1 : 0;
}

static bool ko(bool a, bool b, bool c)
{
    return ho(a) + ho(b) + ho(c) >= 2;
}

Upvotes: 0

endy

Reputation: 3872

int count = 0;

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a)
        count++;
    if (b)
        count++;
    if (c)
        count++;

    return count > 1;
}

Upvotes: 2

Egalitarian

Reputation: 2218

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

return (A && (B || C )) || C;

Upvotes: 1

Bobin

Reputation: 445

Its easy with operator overloading if you have a lot of booleans.

operator fun Boolean.unaryPlus() = if (this) 1 else 0
// ...
if(+bool1 + +bool2 + ... + +boolN > 2) {
    // ...
}

Upvotes: 0

nabil london

Reputation: 521

Another one:

return a? b||c : b&&c

Upvotes: -2

z-index

Reputation: 389

Calculated via a truth table:

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

Upvotes: 4

coder

Reputation: 71

Currenty with Java 8, I really prefer something like this:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return Stream.of(a, b, c).filter(active -> active).count() >= 2;
}

Upvotes: 4

pdox

Reputation: 1

return (a==b) ? a : c;

Explanation:

If a==b, then both are true or both are false. If both are true, we have found our two true booleans, and can return true (by returning a). If both are false there cannot be two true booleans even if c is true, so we return false (by returning a). That's the (a==b) ? a part. What about : c ? Well if a==b is false, then exactly one of a or b must be true, so we have found the first true boolean, and the only thing left that matters is if c is also true, so we return c as the answer.

Upvotes: 162

polygenelubricants

Reputation: 383746

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

JLS 15.25 Conditional Operator ? :

Upvotes: 848

Rotsor

Reputation: 13783

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++)
            {
                sum += majorityDEAD(data[i], data[j], data[k])?1:0; 
                sum += majorityDEAD(data[i], data[k], data[j])?1:0; 
                sum += majorityDEAD(data[j], data[k], data[i])?1:0; 
                sum += majorityDEAD(data[j], data[i], data[k])?1:0; 
                sum += majorityDEAD(data[k], data[i], data[j])?1:0; 
                sum += majorityDEAD(data[k], data[j], data[i])?1:0; 
            }
        }
        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;
        long t0,t1,t2,t3,t4,tDEAD;
        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);

        tDEAD = System.currentTimeMillis();

        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("       DEAD          : " + (tDEAD-t4) + " ms");
        System.out.println("sum: "+sum);
    }

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

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
       DEAD          : 169 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
       DEAD          : 221 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
       DEAD          : 1016 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
       DEAD          : 161 ms

Results from Paul Wagland with a Mac Java 1.6.0_26-b03-383-11A511

a&&b || b&&c || a&&c : 394 ms 
   a ? b||c : b&&c   : 435 ms
   a&b | b&c | c&a   : 420 ms
   a + b + c >= 2    : 640 ms
   a ^ b ? c : a     : 571 ms
   a != b ? c : a    : 487 ms
       DEAD          : 170 ms

Upvotes: 228

David R Tribble

Reputation: 12204

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.

Addendum

Another (slightly optimized) version of this:

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

This might run slightly faster, assuming that the comparison against 0 will use faster (or perhaps less) code than the comparison against 2.

Upvotes: 13

To Kra

Reputation: 3578

public static boolean atLeast(int atLeastToBeTrue, boolean...bools){
    int booleansTrue = 0;
    for(boolean tmp : bools){
        booleansTrue += tmp ? 1 : 0;
    }
    return booleansTrue >= atLeastToBeTrue;
}

You can choose how many at least you want to be true from varargs a.k.a boolean[] :-)

Upvotes: 0

mkobit

Reputation: 47259

Taking another approach to this using Java 8's Stream functionality, for any number of booleans with an arbitrary required amount. The Stream short circuits if it hits the limit before processing all of the elements:

public static boolean atLeastTrue(int amount, Boolean ... booleans) {
    return Stream.of(booleans).filter(b -> b).limit(amount).count() == amount;
}

public static void main(String[] args){
    System.out.println("1,2: " + atLeastTrue(1, true, false, true));
    System.out.println("1,1: " + atLeastTrue(1, false, true));
    System.out.println("1,0: " + atLeastTrue(1, false));
    System.out.println("1,1: " + atLeastTrue(1, true, false));
    System.out.println("2,3: " + atLeastTrue(2, true, false, true, true));
    System.out.println("3,2: " + atLeastTrue(3, true, false, true, false));
    System.out.println("3,3: " + atLeastTrue(3, true, true, true, false));
}

Output:

1,2: true
1,1: true
1,0: false
1,1: true
2,3: true
3,2: false
3,3: true

Upvotes: 1

mdprotacio

Reputation: 842

The simplest form using ternary operators to solve the problem is:

return a ? (b ? true : c) : (b ? c : false);

You may also want to invest finding a solution by using double negation of the requirement, meaning to say, instead of at least two true values, you need to satisfy the condition at most one false value.

Upvotes: 0

Kshitij Banerjee

Reputation: 1748

If I convert the booleans into a number, and if the number is not a power of two, it has at least two trues.

a*4 + b*2 + c*1 = N
return( N != 0 && (N&(N-1)) != 0)

I am just giving an alternative.

Upvotes: 1

Bruce Attah

Reputation: 321

Since it wasn't specified how the code should be improved, I shall endeavour to improve the code by making it more amusing. Here's my solution:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

In case anyone's wondering if this code works, here's a simplification using the same logic:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5;

}

This can be boiled down further to the following:

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

But now it's not funny any more.

Upvotes: 6

d1val

Reputation: 401

How about (a||b) && (a||c) - Java, uses three comparisons instead of the OP's six.

Wrong, I should have checked earlier.

Upvotes: 1

vine'th

Reputation: 5030

We can convert the bools to integers and perform this easy check:

(int(a) + int(b) + int(c)) >= 2

Upvotes: 7

Derek Organ

Reputation: 8473

It seems to me that three out of three are quite arbitrary numbers, and the function should work with an arbitrary number. So in order to answer the question, I'd write a function that would work out if x in an array were true, for example,

bool istrue ( int x, bool[] list)
    y = count true in list
    return y >= x

Upvotes: 0

Dimitre Novatchev

Reputation: 243449

It should be:

(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

Upvotes: 3

Jay

Reputation: 27474

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".

Upvotes: 3

Barzee

Reputation: 905

As an addition to @TofuBeer TofuBeer's excellent post, consider @pdox pdox's answer:

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

Consider also its disassembled version as given by "javap -c":

static boolean five(boolean, boolean, boolean);
  Code:
    0:    iload_0
    1:    iload_1
    2:    if_icmpne    9
    5:    iload_0
    6:    goto    10
    9:    iload_2
   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
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

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

Upvotes: 4

Aaron

Reputation: 9

In 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.

Upvotes: 2

Matt Billenstein

Reputation: 678

This sort of is reading better:

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

Upvotes: 3

Vagif Verdi

Reputation: 4896

In Clojure:

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

Usage:

(at-least 2 true false true)

Upvotes: 7

blakecallens

Reputation: 1

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 three - 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;
}

Upvotes: 5

Roman A. Taycher

Reputation: 19477

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. It is written like this:

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

Upvotes: 9

Check if at least two out of three booleans are true

Answers (30)

References

Related Questions