Lesson 99: BinaryGap (Binary Gap)

Lesson 99: BinaryGap
https://codility.com/programmers/lessons/14

最初のバージョンはこれです。１００％もらえましたね。

ちょっとなぜこの問題の計算量がO(log(N))とされているのか悩みました。'int'はcordialityの環境では３２ビットなので。

おそらく、ループをそれ以上のbinary gapがない時には打ち切って良いのでlog(N)と言ってるのかなと思います。

int solution(int N) 
{
    int max = 0;
    
    int mask = 0x80000000;

    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N << i) & mask;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

で、こちらが途中でループを打ち切るバージョンです。

int solution(int N) 
{
    int max = 0;
    
    int i = 0;

    //find the first 1.
    for (   ; i < sizeof(int) * 8; i++){
        int tmp = (N >> i) & 1;
        if (tmp != 0){
            break;
        }
    }
    
    //no 1 found.
    if (i == sizeof(int) * 8){
        return 0;
    }
    
    //let's seek for the binary gap
    int cnt = 0;
    for (i = i +1; i < sizeof(int) * 8; i++){
        int tmp = (N >> i);
        if (tmp == 0){
            break;
        }
        
        tmp = tmp & 1;
        if (tmp == 0){
            cnt++;    
        }
        else {
            max = max < cnt ? cnt : max; 
            cnt = 0;
        }
    }
       
    return max;
}

そして、より短い版です。


























int solution(int N) {

    

    int max = 0;

    int flg = 0;

    int cnt = 0;

    

    while (N > 0){

        if (N & 1 == 1){

            if (flg == 0){

                flg = 1;

            }

            else {

                max = max < cnt ? cnt : max;

            }

            cnt = 0;

        }

        else {

            cnt++;

        }

        N = N >> 1;

    }

    

    return max;

}