BinaryGap em duas linhas
Caio Vidal
Posted on February 6, 2020
Depois de solucionar o 1° desafio do codility: BinaryGap, resolvi postar aqui o algoritmo final que usei.
A desafio é o seguinte: Dado um número N, deve-se transforma-lo em binário e retornar o tamanho do maior número de zeros entre 1's.
Com exemplo fica mais fácil entender, olha só:
- O número 152 em binário fica: 1 00 11000 - Ele possui apenas 1 bloco com dois zeros, então o retorno seria 2.
- O número 15 em binário fica: 1111 - Ele não possui nenhum bloco de zeros, então o retorno seria 0.
- O número 3561 em binário fica: 11 0 1111 0 1 00 1- Ele possui 2 blocos com um zero e um bloco com dois zeros, o retorno então seria 2.
Dado o desafio, depois de um tempo tentando soluções com loop e contadores, cheguei a minha 1ª solução que achei aceitável:
function solution(N) {
const n = "X" + N.toString(2) + "X";
const list = n.split("1");
let max = 0;
list.forEach((i) => {
if (i.indexOf("X") == -1) {
max = i.length > max ? i.length : max;
}
})
return max;
}
Depois dessa solução, ficou fácil, bastou alterar o forEach para um map e um reduce, olha aí:
function solution(N) {
const n = "X" + N.toString(2) + "X";
return n.split("1").map((i) => i.indexOf("X") == -1 ? i.length : 0)
.reduce((a, b) => Math.max(a, b))
}
O map retorna o length de cada bloco e o reduce retorno o maior número do array.
Lembrando que embora a solução final tenha ficado mais elegante, a solução mais performática é a 1ª pois existe apenas uma iteração.
Um abraço e até a próxima.
Posted on February 6, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
October 2, 2024
October 11, 2024