Categorías
Algorithms

Problema de codilidad de Twitter: brecha binaria máxima

Problema: Obtenga el máximo espacio binario.

Por ejemplo, la forma binaria de 9 es 1001, el espacio es 2.

Solución Java 1

Un entero x & 1 obtendrá el último dígito del entero.

public static int getGap(int N) {
	int max = 0;
	int count = -1;
	int r = 0;
 
	while (N > 0) {
		// get right most bit & shift right
		r = N & 1;
		N = N >> 1;
 
		if (0 == r && count >= 0) {
			count++;
		}
 
		if (1 == r) {
			max = count > max ? count : max;
			count = 0;
		}
	}
 
	return max;
}

El tiempo es O (n).

Solución Java 2

public static int getGap(int N) {
	int pre = -1;
	int len = 0;
 
	while (N > 0) {
		int k = N & -N;
 
		int curr = (int) Math.log(k);
 
		N = N & (N - 1);
 
		if (pre != -1 && Math.abs(curr - pre) > len) {
			len = Math.abs(curr - pre) + 1;
		}
		pre = curr;
	}
 
	return len;
}

El tiempo es O (log (n)).

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *