Complejidad: O(n log n)
public class FakeCoin {
/**
* @author Esteban Montes Morales - A.K.A "Sanko"
* UniOvi problem
*/
public static int fakeCoinRec(int[] v, int l, int r){
int n = r-l;
if((n+1)<3) return -1;
else if((n+1)==3){
if(v[l] == v[l+1] && v[l] != v[r]) return r;
else if(v[l+1] == v[r] && v[r] != v[l]) return l;
else if(v[l] == v[r] && v[l+1] != v[l]) return l+1;
else return -1;
}
else if((n+1)>3 && (n+1)<7){
if(FakeCoin.fakeCoinRec(v, l, r-1) == -1){
if(v[l]==v[r]) return -1;
return r;
}else return FakeCoin.fakeCoinRec(v, l, r-1);
}
else if((n+1)>6){
int[] v1 = FakeCoin.copyVector(v, l, ((n+1)/2)-1);
int[] v2 = FakeCoin.copyVector(v, (n+1)/2, r);
int a = FakeCoin.fakeCoinRec(v1, 0, v1.length-1);
int b = FakeCoin.fakeCoinRec(v2, 0, v2.length-1);
return b==-1 ? a: v1.length+b;
}
return -1;
}
public static int[] copyVector(int[] v, int from, int to){
int[] copy = new int[(to-from)+1];
for(int i=from; i<to+1; i++){
copy[i-from] = v[i];
}
return copy;
}
}
Prueba unitaria básica: (Ejecutar Nveces)
import static org.junit.Assert.*;
import java.util.Random;
import org.junit.Test;
import junit.framework.Assert;
public class FakeCoinTest {
@Test
public void test() {
int[] vector = new int[100000];
for(int i=0; i<vector.length; i++){
vector[i] = 1;
}
Random r = new Random();
int valor = r.nextInt(100000);
vector[valor] = 0; // insertamos la moneda falsa
assertEquals(valor, FakeCoin.fakeCoinRec(vector, 0, vector.length-1));
}
}