Lacuna-Binaria
Este foi um exercicio feito em Java para treinamento.
Descrição da tarefa: Uma lacuna binária dentro de um inteiro positivo N é qualquer sequência máxima de zeros consecutivos que é cercada por uns em ambas as extremidades na representação binária de N.
Por exemplo, o número 9 tem representação binária 1001 e contém uma lacuna binária de comprimento 2. O número 529 tem representação binária 1000010001 e contém duas lacunas binárias: uma de comprimento 4 e uma de comprimento 3. O número 20 tem representação binária 10100 e contém uma lacuna binária de comprimento 1. O número 15 tem representação binária 1111 e não tem lacunas binárias. O número 32 tem representação binária 100000 e não tem lacunas binárias.
Escreva uma função:
classe Solução { public int solução(int N); }
que, dado um inteiro positivo N, retorna o comprimento de sua maior lacuna binária. A função deve retornar 0 se N não contiver uma lacuna binária.
Por exemplo, dado N = 1041, a função deve retornar 5, porque N tem representação binária 10000010001 e, portanto, seu maior intervalo binário tem comprimento 5. Dado N = 32, a função deve retornar 0, porque N tem representação binária '100000' e, portanto, não há intervalos binários.
Escreva um algoritmo eficiente para as seguintes suposições:
N é um número inteiro dentro do intervalo [ 1 .. 2.147.483.647 ].
class Solution {
public int solution(int N) {
String binaryN = Integer.toBinaryString(N);
int maxGap = 0;
int currentGap = 0;
boolean inGap = false;
for (int i = 0; i < binaryN.length(); i++) {
char c = binaryN.charAt(i);
if (c == '0') {
if (!inGap) {
inGap = true;
}
currentGap++;
} else {
if (inGap) {
maxGap = Math.max(maxGap, currentGap);
currentGap = 0;
inGap = false;
}
}
}
return maxGap;
}
}
Converter o inteiro N para sua representação binária. Podemos usar a função Integer.toBinaryString(N) em Java para isso.
Encontrar todas as lacunas binárias. Iteramos pela string binária, procurando sequências consecutivas de zeros. Uma lacuna binária começa quando encontramos um '0' após um '1' e termina quando encontramos um '1' após um ou mais '0's.
Calcular o comprimento de cada lacuna binária. Para cada lacuna encontrada, calculamos o número de zeros consecutivos.
Encontrar a maior lacuna binária. Mantemos um valor máximo que é atualizado sempre que encontramos uma lacuna maior que a atual.
Retornar o comprimento da maior lacuna binária. Se nenhuma lacuna binária for encontrada, retornamos 0.
Link do repositorio: dangrag/Lacuna-Bin-ria: Este foi um exercicio feito em Java para treinamento
