-
Notifications
You must be signed in to change notification settings - Fork 0
/
2-09-solounimpar.cpp
68 lines (52 loc) · 1.39 KB
/
2-09-solounimpar.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// Nuria Bango Iglesias
// VJ04
#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
using namespace std;
// dado un vector de numeros enteros positivos y consecutivos del que se han eliminado todos los elementos impares menos uno
// encuentre cual es ese numero impar que ha quedado en el vector
// O(log n) donde n es el numero de elementos del vector v
int elementoImpar(const vector<int>& v, int ini, int fin) {
int n = fin - ini;
// caso base: un elemento
if (n == 1)
return v[ini];
// caso base: el elemento que buscamos es ini
if (v[ini] % 2 != 0)
return v[ini];
int mitad = (fin + ini) / 2;
// caso base: el elemento que buscamos es mitad
if (v[mitad] % 2 != 0)
return v[mitad];
// si el elemento mitad es mayor o igual que el elemento que deberia estar
// en esa posicion (tomando como referencia ini) se busca en la mitad derecha
if (v[mitad] >= v[ini] + 2 * (mitad - ini))
return elementoImpar(v, mitad + 1, fin);
else
return elementoImpar(v, ini + 1, mitad);
}
bool resuelveCaso() {
int n;
cin >> n;
if (n == 0)
return false;
vector<int> v(n);
for (int& e : v)
cin >> e;
cout << elementoImpar(v, 0, n) << "\n";
return true;
}
int main() {
#ifndef DOMJUDGE
std::ifstream in("datos.txt");
auto cinbuf = std::cin.rdbuf(in.rdbuf());
#endif
while (resuelveCaso());
#ifndef DOMJUDGE
std::cin.rdbuf(cinbuf);
system("PAUSE");
#endif
return 0;
}