Test results - Codility

Tasks Details

easy

1. BinaryGap

Find longest sequence of zeros in binary representation of an integer.

Task Score

100%

Correctness

100%

Performance

Not assessed

A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N.

For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps.

Write a function:

function solution(N);

that, given a positive integer N, returns the length of its longest binary gap. The function should return 0 if N doesn't contain a binary gap.

For example, given N = 1041 the function should return 5, because N has binary representation 10000010001 and so its longest binary gap is of length 5. Given N = 32 the function should return 0, because N has binary representation '100000' and thus no binary gaps.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..2,147,483,647].

Solution

Programming language used JavaScript

Time spent on task 26 minutes

Notes

not defined yet

Task timeline

Code: 01:23:09 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert
    let binary = parseInt(N, 2);
    console.log(binary)
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

RUNTIME ERROR
tested program terminated unexpectedly

0.142 s

RUNTIME ERROR, tested program terminated unexpectedly

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

▶

example2
example test n=15=1111_2

✘

RUNTIME ERROR
tested program terminated unexpectedly

0.146 s

RUNTIME ERROR, tested program terminated unexpectedly

stderr:

Invalid result type, integer expected, 'undefined' found
Perhaps you are missing a 'return'?

stdout:

Code: 01:23:24 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert
    let binary = parseInt(N, 2);
    console.log(binary)
    
    return 0
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.130 s

WRONG ANSWER, got 0 expected 5

stdout:

▶

example2
example test n=15=1111_2

✔

0.128 s

stdout:

Code: 01:23:44 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert
    let binary = parseInt(N, 2);
    console.log('binary',binary)
    
    return 0
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.141 s

WRONG ANSWER, got 0 expected 5

stdout:

binary 2

▶

example2
example test n=15=1111_2

✔

0.138 s

stdout:

binary 1

Code: 01:26:27 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    console.log('binary',binary)
    
    return 0
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.137 s

WRONG ANSWER, got 0 expected 5

stdout:

binary 10000010001

▶

example2
example test n=15=1111_2

✔

0.136 s

stdout:

binary 1111

Code: 01:36:06 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    // console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        if (binary[i] === 1){
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current > -1) {
            // if we have a zero and have started a sequene then increment the current
            current++
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.136 s

WRONG ANSWER, got 0 expected 5

▶

example2
example test n=15=1111_2

✔

0.134 s

Code: 01:36:37 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        console.log('binary[i]',binary[i])
        if (binary[i] === 1){
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current > -1) {
            // if we have a zero and have started a sequene then increment the current
            current++
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.136 s

WRONG ANSWER, got 0 expected 5

stdout:

binary 10000010001
binary[i] 1
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 1
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 1

▶

example2
example test n=15=1111_2

✔

0.136 s

stdout:

binary 1111
binary[i] 1
binary[i] 1
binary[i] 1
binary[i] 1

Code: 01:37:51 UTC, js, verify, result: Failed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        console.log('binary[i]',binary[i])
        if (binary[i] === 1){
            console.log('start at',i)
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                console.log('end at',i)
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current >= 0) {
            // if we have a zero and have started a sequene then increment the current
            current++
            console.log('increase current',current)
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✘

WRONG ANSWER
got 0 expected 5

0.144 s

WRONG ANSWER, got 0 expected 5

stdout:

binary 10000010001
binary[i] 1
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 1
binary[i] 0
binary[i] 0
binary[i] 0
binary[i] 1

▶

example2
example test n=15=1111_2

✔

0.140 s

stdout:

binary 1111
binary[i] 1
binary[i] 1
binary[i] 1
binary[i] 1

Code: 01:39:01 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        console.log('binary[i]',binary[i])
        if (binary[i] == 1){ // using == so that string is auto-converted to int for us in comparrison
            console.log('start at',i)
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                console.log('end at',i)
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current >= 0) {
            // if we have a zero and have started a sequene then increment the current
            current++
            console.log('increase current',current)
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✔

0.148 s

stdout:

binary 10000010001
binary[i] 1
start at 0
binary[i] 0
increase current 1
binary[i] 0
increase current 2
binary[i] 0
increase current 3
binary[i] 0
increase current 4
binary[i] 0
increase current 5
binary[i] 1
start at 6
end at 6
binary[i] 0
increase current 1
binary[i] 0
increase current 2
binary[i] 0
increase current 3
binary[i] 1
start at 10

▶

example2
example test n=15=1111_2

✔

0.144 s

stdout:

binary 1111
binary[i] 1
start at 0
binary[i] 1
start at 1
binary[i] 1
start at 2
binary[i] 1
start at 3

Code: 01:42:07 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        // we can using == so that string is auto-converted to int for us in comparrison
        if (binary[i] == 1){ 
            console.log('start at',i)
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current >= 0) {
            // if we have a zero and have started a sequence then increment the current
            current++
            console.log('increase current',current)
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✔

0.144 s

stdout:

binary 10000010001
start at 0
increase current 1
increase current 2
increase current 3
increase current 4
increase current 5
start at 6
increase current 1
increase current 2
increase current 3
start at 10

▶

example2
example test n=15=1111_2

✔

0.142 s

stdout:

binary 1111
start at 0
start at 1
start at 2
start at 3

Code: 01:42:33 UTC, js, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    // console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        // we can using == so that string is auto-converted to int for us in comparrison
        if (binary[i] == 1){ 
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current >= 0) {
            // if we have a zero and have started a sequence then increment the current
            current++
        }
    }
    
    return longest
}

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✔

0.138 s

▶

example2
example test n=15=1111_2

✔

0.138 s

Code: 01:42:37 UTC, js, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');

function solution(N) {
    // write your code in JavaScript (Node.js 6.4.0)
    
    // HINT: Convert 
    let binary = N.toString(2)
    // console.log('binary',binary)
    
    var longest = 0
    var current = -1 // use minus 1 to indicate that we are not yet counting
    for (let i = 0; i < binary.length; ++i){
        // two cases, we encounter a 1 or a zero
        // we can using == so that string is auto-converted to int for us in comparrison
        if (binary[i] == 1){ 
            // if a 1 then we are either terminating a sequence or starting one
            if (current > longest) {
                // if terminating then we set our new maximum
                longest = current
                // we can also terminate early, if it is not possible to encounter a longer sequence
                if (longest > binary.length - i ) break
            }
            // set current to zero for the new sequence
            current = 0
        } else if (current >= 0) {
            // if we have a zero and have started a sequence then increment the current
            current++
        }
    }
    
    return longest
}

Analysis summary

The solution obtained perfect score.

Analysis

expand all Example tests

▶

example1
example test n=1041=10000010001_2

✔

0.139 s

▶

example2
example test n=15=1111_2

✔

0.136 s

expand all Correctness tests

▶

extremes
n=1, n=5=101_2 and n=2147483647=2**31-1

✔

0.135 s

0.141 s

0.143 s

▶

trailing_zeroes
n=6=110_2 and n=328=101001000_2

✔

0.137 s

0.138 s

▶

power_of_2
n=5=101_2, n=16=2**4 and n=1024=2**10

✔

0.138 s

0.137 s

▶

simple1
n=9=1001_2 and n=11=1011_2

✔

0.140 s

0.139 s

▶

simple2
n=19=10011 and n=42=101010_2

✔

0.137 s

▶

simple3
n=1162=10010001010_2 and n=5=101_2

✔

0.138 s

0.139 s

▶

medium1
n=51712=110010100000000_2 and n=20=10100_2

✔

0.137 s

▶

medium2
n=561892=10001001001011100100_2 and n=9=1001_2

✔

0.136 s

▶

medium3
n=66561=10000010000000001_2

✔

0.137 s

▶

large1
n=6291457=11000000000000000000001_2

✔

0.136 s

▶

large2
n=74901729=100011101101110100011100001

✔

0.137 s

▶

large3
n=805306373=110000000000000000000000000101_2

✔

0.137 s

▶

large4
n=1376796946=1010010000100000100000100010010_2

✔

0.137 s

▶

large5
n=1073741825=1000000000000000000000000000001_2

✔

0.137 s

▶

large6
n=1610612737=1100000000000000000000000000001_2

✔

0.140 s