Једно решење може бити засновано на линеарној претрази свих кандидата. Оно подразумева да су сви елементи учитани у низ (што, додуше, нарушава услов који је дат у поставци задатка). За све бројеве од \(0\) до \(n\) проверавамо да ли су садржани у низу.
У језику C++ линеарну претрагу можемо реализовати библиотечком функцијом find којој се прослеђују итератори на део низа који се претражује и вредност која се тражи. Функција ће вратити итератор на пронађено прво појављивање елемента или итератор који указује непосредно иза краја претраженог распона, ако елемент не постоји.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
for (int x = 0; x <= n; x++)
if (find(begin(a), end(a), x) == end(a)) {
cout << x << endl;
break;
}
return 0;
}Сложеност. Пошто су елементи учитани у низ дужине \(n\), меморијска сложеност је \(O(n)\).
Линеарна претрага низа од \(n\) елемената у најгорем случају захтева \(O(n)\) корака, па пошто се тражи \(n + 1\) елемент, сложеност је \(O(n^2)\). Може се приметити и да није могуће да се у сваком кораку линеарне претраге догоди најгори случај. Најгори случај се дешава када се елемент не налази у низу, а сви елементи који се траже (сем једног) су присутни. Заиста, када тражимо елемент који се налази на позицији \(i\) та претрага ће се завршити у \(i\) корака. Прецизније, елемент на позицији 1 ће се пронаћи у једном кораку, елемент на позицији 2 у два корака, елемент на позицији 3 у три корака и тако даље. Укупан број корака је зато \(1 + 2 + \ldots + n\), што је опет \(O(n^2)\).
Нагласимо да не треба да нас завара случај када се линеарна претрага имплементира коришћењем библиотечке функције. Иако тада у главном делу програма постоји само једна петља, у њој се позива функција линеарне сложености, па је укупна сложеност квадратна (кажемо да се појављује скривена сложеност).
Разним техникама временска сложеност се може свести на \(O(n)\), а циљ нам је и да меморијску сложеност сведемо на \(O(1)\).
Збир свих елемената из скупа \(\{0, 1, 2, \ldots, n\}\) је \(0 + 1 + 2 + \ldots + n = \frac{n(n+1)}{2}\). То је збир елемената који се налазе у низу и недостајућег елемента. Недостајући елемент је, дакле, једнак, разлици између \(\frac{n(n+1)}{2}\) и збира свих елемената низа. Потребно је обратити пажњу на то да је за израчунавање збира елемената потребно користити бар 64-битни целобројни тип.
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
long long zbir = 0;
for (int i = 0; i < n; i++) {
int x; cin >> x;
zbir += x;
}
long long zbir_svih = ((long long)n) * (n+1) / 2;
int nedostajuci = zbir_svih - zbir;
cout << nedostajuci << endl;
return 0;
}Сложеност. Збир свих елемената лако можемо израчунати у времену \(O(n)\), приликом учитавања (без смештања елемената у низ, па је меморијска сложеност \(O(1)\)).
Ово решење би се могло уопштити и на случај када знамо да недостају два броја од \(0\) до \(n\). Тада бисмо уз збир израчунали и збир квадрата, а затим решавањем система две једначине са две непознате могли израчунати бројеве који недостају.