Este problema me lo pusieron en una entrevista de trabajo, así que imaginad los nervios y las prisas para resolver. Para poder hacerlo en condiciones similares de nerviosismo recomiendo tomar 2 red bulls y resolverlo desnudo en el balcón tras gritar "vecinoooooos cabrooones".
El problema original era que te dan un conjunto de números [x1, x2, x3,....] tales que para todo número el conjunto contiene su negativo, excepto para uno. Por ejemplo [1,-7,-9,9,13,2,-13,1,7]. Lo que pedían era hacer hacer una fórmula tal que la solución fuese aquel número no negado. Fácil, contesté, el sumatorio me lo resuelve.
Muy bien, aquí tienes tu azucarillo, me dijeron. Y vino la segunda parte que era la de verdad. Ahora te damos un conjunto de números tales que todo número está repetido dos veces excepto uno, por ejemplo [1,7,9,9, 13,2,13,1,7]. Queremos lo mismo, una fórmula tal que encontremos ese número no repetido, y con la misma sencillez que la anterior.
Si eres informático: básicamente solamente tienes espacio de memoria para un número, así que nada de diccionarios. La solución es matemática.
Comentarios
#17 Sencillo: fallé como un campeón
#18 Normal. Si es que hay que ser cabrón para poner eso en una entrevista....
#19 Era Amazon.
#20 Tú también fallaste!!! Gatito Lindo.
#23 Ya lo entiendo... si lo pasas a binario, te puedes fijar solo en la columna de cada digito binario... como todos los números aportan su bit dos veces a "esa" columna, solo sobrevivirá el bit que aparezca una vez.
Cada columna reconstruye al número solitario.
Todos son impares menos el buscado. ¿Supongo que es casualidad?
#6 Es casualidad...
Se me ocurre una solución a bote pronto que no sé si cumple con los requisitos pero creo que podría valer. La idea es hacer una función que recorra el array v[]:
Selecciono el primer valor v[0]
Recorro el array hasta el final restando cada valor
Si la resta v[0]-v[i] es 0 entonces llamo recursivamente a la función con un vector sin esos valores.
La condición de parada sería que el vector únicamente tenga un valor el cual sería el desemparejado.
Luego habría que comprobar la longitud en cada iteración etc.
Si lo pienso un poco más seguro que le saco alguna pega.
#1 Me falto dejar claro que cada elemento solamente lo puedes mirar una vez. Si la primera parte se resuelve con un "sumatorio", la segunda debe resolverse también con una operación matemática, así sin más.
P.D. De hecho recuerda que solamente tienes memoria para un número, una llamada recursiva significa como mínimo si pasas los arrays por referencia, un entero completo para referenciar a la función, dentro del stack.
#2 sabía yo que por ahí no iban los tiros.
#1 #3 Lo pondré más claro... si los números son x1, x2, x3, x4... hay que encontrar una operación * tal que:
x1*x2*x3*x4*... = el número que buscamos.
En el primer ejemplo la operación era la suma. En el segundo, ¿cuál será?
Multiplicas todos, sacas factores comunes y ... hora de cenar
#8 Nopis, eso es una operación complicada. Te juro que es sencilla. Por ponerlo en código:
function solucion(int[] numbers)
return result;
}
Hay que buscar lo que va en esos ???.
#9 Un triste xor! Que cabronada
#10 Jajajajaja, a que mola que la solución sea tan simple?
#11 Digna de entrevista
#11 ¿Y como has podido deducir esa operación en la entrevista? ¿Tuviste que pasar los numero a binario y hacer los calculos o existe alguna regla del XOR especial para este tipo de situaciones?
La verdad es que es puñetera la pregunta y para una entrevista ya ni te cuento (con los nervios y tal).
#10 Joder cabronazo, mil puntos para ti.
#8 con lo que dices si el número que buscas es un 12... Tu dirás que es un 3.
#13 Bueno... el puesto es para becario... ¡Contratado!
#13 Andaba perdido por otros andurriales. Me gustan los problemas pero la teoría hay que currarsela...
Si intentas dividir un numero entre otro del array y te da distinto de 1 sigues probando, si te da 1 ya has encontrado 2 numeros iguales y los descartas... hasta quedarte con un número sólo ?
Basta con sumar todos los números del array. El resultado será siempre el número que no tenga negativo.
#14 No has leído el enunciado entero. Los números no tienen negativo, simplemente están duplicados.
#15 Lo se lo se. Me he dado cuenta tarde y no he podido eliminar el comentario. Gracias de todas formas.