Codility: Condition in comfort

Question

While conducting the examination this was one of the task (which I could not solve):

They say a number A "comfort" to another number B if, when you convert both numbers to binary, all positions in B where there is a number 1 must be another 1 in the same position in A.

example:

B = 101 A = 111

In this case, the number A "comfort" to B, however

B = 101 A = 011

The Comfort condition is not met.

They gave me 3 unsigned numbers with 30 bits A, B and C, between 0 and 2 ^ 30. I must determine the amount of numbers in that range that meet the condition of "comfort" for at least one of those numbers.

expected worst-case time complexity is O (log (A) + log (B) + log (C));

I use the following code and it takes too long, most of all because it checks the binary number as an array and compare every cell. I assume there must be some way to make it faster (some math operation or idk :-( ).

public class Main {
public static void main(String[] args) 
{
    sol(905,5000,11111111); //I used any numbers
}

public static void sol(int A, int B, int C)
{

    int min=Math.min(A, Math.min(B, C)); 
    int max=(int) Math.pow(2, 30);

    String binA=Integer.toBinaryString(A); binA=fillBin(binA);
    String binB=Integer.toBinaryString(B); binB=fillBin(binB);
    String binC=Integer.toBinaryString(C); binC=fillBin(binC);

    String binMax=Integer.toBinaryString(max);

    int conta=0;

    for(int i=min;i<=max;i++)
    {
        String binT = Integer.toBinaryString(i);binT=fillBin(binT);

        boolean failA=false;
        boolean failB=false;
        boolean failC=false;

        for(int j=0;j<binT.length();j++)
        {
            if((binA.length()<j)&&(binB.length()<j)&&(binC.length()<j))
            {
                break;
            }

            if((!failA)||(!failB)||(!failC))
            {
                if((binA.length()<j)&&(binA.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failA=true;
                }
                if((binB.length()<j)&&(binB.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failB=true;
                }
                if((binC.length()<j)&&(binC.charAt(j)=='1') && (binT.charAt(j)!='1'))
                {
                    failC=true;
                }
            }
            else
            {
                break;

            }
        }

        if((!failA)||(!failB)||(!failC))
        {
            conta++;
        }
    }

}

private static String fillBin(String binA) 
{
    String S=binA;
    for(int i=0;i<(31-binA.length());i++)
    {
        S="0"+S;
    }       
    return S;
}

}

If any of you already done this task before and see that there are some missing data , let me know , excuse my English (not my native language).

thank you very much

EDIT: This is the code with @Eran 's help:

public class BinaryTask 

{ public void test(int A, int B, int C) { long timeStart, timeEnd; timeStart = System.currentTimeMillis();

    //Bunch of variables
    String binaryA = Integer.toBinaryString(A); int zerosA=0;
    String binaryB = Integer.toBinaryString(B); int zerosB=0;
    String binaryC = Integer.toBinaryString(C); int zerosC=0;

    String binaryAB =""; int zerosAB=0;
    String binaryBC =""; int zerosBC=0;
    String binaryAC =""; int zerosAC=0;

    String binaryABC=""; int zerosABC=0;

    //The long for the for
    int Max = Math.max(binaryA.length(), Math.max(binaryB.length(), binaryC.length()));

    //Creating: A|B, B|C, A|B and A|B|C that meet the confort condition
    for(int i=0;i<Max;i++)
    {
        //Creating A|B
        if((binaryA.length()>i)&&(binaryB.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryB.charAt(i)=='1'))
            {
                binaryAB="1"+binaryAB;
            }
            else //I also count this zero so i dont have the do another for later
            {
                binaryAB="0"+binaryAB; zerosAB++;
            }
        }
        //Creating B|C
        if((binaryB.length()>i)&&(binaryC.length()>i))
        {
            if((binaryB.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryBC="1"+binaryBC;
            }else{binaryBC="0"+binaryBC; zerosBC++;}
        }
        //Creating A|C
        if((binaryA.length()>i)&&(binaryC.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryAC="1"+binaryAC;
            }else{binaryAC="0"+binaryAC;zerosAC++;}
        }
        //Creating A|B|C
        if((binaryA.length()>i)&&(binaryB.length()>i)&&(binaryC.length()>i))
        {
            if((binaryA.charAt(i)=='1')||(binaryB.charAt(i)=='1')||(binaryC.charAt(i)=='1'))
            {
                binaryABC="1"+binaryABC;
            }else{binaryABC="0"+binaryABC; zerosABC++;}
        }
    }

    //Counting the other amount of zeros
    zerosA = countZeros(binaryA);
    zerosB = countZeros(binaryB);
    zerosC = countZeros(binaryC);

    long confortA = (long) Math.pow(2, zerosA);
    long confortB = (long) Math.pow(2, zerosB);
    long confortC = (long) Math.pow(2, zerosC);
    long confortAB = (long) Math.pow(2, zerosAB);
    long confortBC = (long) Math.pow(2, zerosBC);
    long confortAC = (long) Math.pow(2, zerosAC);
    long confortABC = (long) Math.pow(2, zerosABC);

    long totalConfort = confortA + confortB + confortC - confortAB - confortBC - confortAC + confortABC;
    timeEnd = System.currentTimeMillis();

    System.out.println("Total of confort for A "+A+" B "+B+" C "+C+" is " +totalConfort);
    System.out.println("the task has taken "+ ( timeEnd - timeStart ) +" milliseconds");    
}

private int countZeros(String binary) 
{
    int count=0;
    for(int i=0;i<binary.length();i++)
    {
        if(binary.charAt(i)=='0')
        {count++;}
    }
    return count;
}

}

To make a test, i did this:

    public static void main(String[] args) 
{
    BinaryTask T = new BinaryTask();

    int A = (int) Math.pow(2, 10);
    int B = (int) Math.pow(2, 15);
    int C = (int) Math.pow(2, 30);
    T.test(A, B, C);
}

And this was the output:

Total of confort for A 1024 B 32768 C 1073741824 is 1073739776 the task has taken 1 milliseconds

Answer 1

Building on @alain's answer, comf(A) = 2^(number of zero bits in A) is the number of comforting numbers for A.

You need the number of comforting numbers for either A, B or C.

That's comf(A)+comf(B)+comf(C)-comf(A and B)-comf(B and C)-comf(A and C)+comf(A and B and C).

where comf(A and B) denotes the number of comforting numbers for both A and B. and comf(A and B and C) denotes the number of comforting numbers for all A, B and C.

We know how to calculate comf(A), comf(B) and comf(C).

comf(A and B) = 2^(number of zero bits in A|B), since a number X comforts both A and B if and only if it has ones in all the bits for which either A or B has ones.

Similarly, comf(A and B and C) = 2^(number of zero bits in A|B|C).

Since all the calculations are bit operations on A,B and C, the running time is the lengths in bits of A, B and C, which is O (log (A) + log (B) + log (C)).

Answer 2

The condition for 'A comfort to B' is

B & A == B

You could just count the number n of 0 bits in B, and then you have 2^n or Math.pow(2, n) possibilities to build a 'comforting' number A. Unfortunately, this doesn't work for 'comforting to at least one of three numbers', but it could be a starting point.

Answer 3

Are you sure the output Total of confort for A 1024 B 32768 C 1073741824 is 1073739776 is correct ? I do agree with bitwise operation, with that I am getting different retult btw.

public static int solution(int A,int B,int C){
    int total = 0;
    int totalA=0,totalB=0,totalC=0;
    //int max = Math.max(Math.max(A, B), C);
    double limit = Math.pow(2,30);
    for(int i=0;i<=limit;i++){
        int no = A & i;
        if(no == A){
            total++;
            totalA++;
            //continue;
        }
        no = B & i;
        if(no == B){
            total++;
            totalB++;
            //continue;
        }
        no = C & i;
        if(no == C){
            total++;
            totalC++;
            //continue;
        }
    }
    System.out.println("totalA: " + totalA + " totalB:  " + totalB + " totalC: " + totalC);
    total = totalA + totalB + totalC;
    return total;
}

It gives me totalA: 536870912 totalB: 536870912 totalC: 1 1073741825