Se citește un număr natural n (1≤n≤31 ) și k≤1000000, și apoi k numere naturale de forma 2^{p} (0≤p≤30). Se cere să se afișeze pe ecran numărul care ar apărea pe poziția n în șirul ordonat strict crescător obținut din toate numerele distincte aflate pe a doua linie a fișierului. Dacă șirul are mai puțin de n termeni distincţi, se afișează pe ecran mesajul Nu exista. Pentru determinarea numărului cerut se utilizează un algoritm eficient din punctul de vedere al timpului de executare. Exemplu: dacă n=4, k=9 și numerele 2^{2} 2^{5} 2^{0} 2^{5} 2^{3} 2^{2} 2^{1} 2^{2}atunci pe ecran se afișează valoarea 8.

Program C:

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

//Calculeaza log2(x), unde x este o putere a lui 2

int lg2p(unsigned x) {

if (x == 0) return -1;

int bk = 0;

while ((x & 1) == 0) {

 ++bk;

 x >>= 1;

}

return bk;

}

int main() {

unsigned dim, n, tmp;

//Citire pozitie

scanf("%u", &n);

//Citire dimensiune vector

scanf("%u", &dim);

//Citire elemente, calculare valori bucket

int bkt[31] = {0};

for (unsigned i = 0; i < dim; i++) {

 scanf("%u", &tmp);

 ++bkt[lg2p(tmp)];

}

//Afisare rezultat

int curent=0;

int idbkt = 0;

while (curent < n) {

 curent += bkt[idbkt++];

}

printf("%u", 1 << idbkt);

}

Explicatie :

Stiind ca toate numerele sunt o putere a lui 2 putem calcula usor logaritm in baza 2 al fiecarui numar.

Folosim un vector de frecventa in care memoram cate numere de acelasi fel exista pentru orice putere a lui 2. Putem apoi determina rapid ce numar se afla pe orice index.

Vezi counting sort.

Nota :

Se considera ca [tex]n\leq k[/tex]