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

It seems like there was no need for the binary representation of the AB, AC, BC, ABC, since all you needed was the zero count. Or did I miss something? Thanks for posting the question. — peter n, Jun 25 '14 at 05:59
The question indicates that A, B and C are 30 bit long numbers. 2^30 has the 31st bit set and overflows the 30-bit limit. Which is the correct question, 2^30 or 30-bits? — Eusebio Rufian-Zilbermann, Nov 17 '14 at 07:07

score 3 · Accepted Answer · answered Apr 30 '14 at 21:43

3

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

answered Apr 30 '14 at 21:43

Eran

387,369
54
702
768

Thank you! I just edit the post so you can see what I did. If you think there is something more that can be optimized, let me know (also check please this is what you mentioned me, as I dont have the problem's example, I have no way to check if the result is as expected). – Fingolricks May 01 '14 at 20:22
@Fingolricks You have an error in the end `- confortABC` should be `+ confortABC`. – Eran May 01 '14 at 20:34
@Fingolricks In addition, it's not clear why you are converting the numbers to binary Strings. It's much simpler to work with integers. For example, `int binaryAorB = A|B`; – Eran May 01 '14 at 20:36
Thx man, i fixed the problem with de `-confortABC`. And, about the BinaryString, Sorry, maybe I'm not understanding, if I have an integer A and an integer B, the term A | B returns me the binary subset of the two? I have never used the | for something different from the conditions (condition)||(condition). And Well, I make it BinaryString because there is no function in java to convert it into Binary (not sure if it's faster to do the method of Integer to Binary or do it like i'm doing it right now). What you suggest? :-( – Fingolricks May 01 '14 at 22:17
@Fingolricks A|B performs a bit-wise or, which is exactly what you need. For example, 2|3=3 (since 010|011=011). You should read about binary operators in java. And you can find the number of zeroes in the binary representation of the int without converting it to string. You can read about it [here](http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer). – Eran May 01 '14 at 22:39
Ok, I read a little and rather I could find was the number of '1 'is in the binary representation of the number. With do subtraction "length binary number" - Integer.bitCount (number) should be sufficient, but still I see that I have to convert the number into a binarystring It should be something like this: `int confortA = (int) Math.pow(2, (lenghtBinaryA-Integer.bitCount(A)));` – Fingolricks May 02 '14 at 02:22
there is anyway i can ask you to help me with another Codility program? (You were highly didactic with this answer and I'm sure you can help me with the other. – Fingolricks May 02 '14 at 21:42
@Fingolricks You can always post a new question, and someone will probably answer it. If I find the time (and know the answer), that someone might even be me :) – Eran May 02 '14 at 22:17
I already did it :-( [link](http://stackoverflow.com/questions/23370613/codility-binary-period), at the same momento i did this one, 3 days ago :'(, 74 views and no one answer it. If i had at least 50 rep. point i would give a bounty for it. But well, i'm new at this. – Fingolricks May 03 '14 at 01:19

alain · Answer 2 · 2014-04-30T21:18:04.747

1

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.

edited Apr 30 '14 at 21:18

answered Apr 30 '14 at 21:03

alain

11,939
2
31
51

score 0 · Answer 3 · answered Jun 18 '14 at 13:17

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

Codility: Condition in comfort

3 Answers3