Programming Interview: Angka yang Hilang

[Darkc0der]

Soal interview ini ada 2 tahap, ...



Soal pertama (udah kejawab veehunt)

Diketahui ada sebuah const array berukuran n-1 elemen. Tiap elemen di array ini diisi sebuah bilangan yg dipilih dari range 1 s/d n secara acak. Tidak ada 2 elemen array yg nilainya sama.



Jadi, bisa dipastikan bahwa dari bilangan di range 1 s/d n, ... ada persis 1 bilangan yg tidak muncul dalam array di atas.



Berikan sebuah algoritma yg lebih baik dari O(n^2) yg menggunakan space constant untuk menemukan bilangan yg hilang ini. Juga tidak diperbolehkan mengubah array input.



Space constant artinya suatu variable yg size-nya konstan, e.g.: int x, atau int x[5]. Contoh space yg tidak konstan: int* a = new int[n];



Soal kedua (udah kejawab lennie_2nd, w/ honorable mention to veehunt)

Persoalan yg intinya sama, tapi array sizenya n-2 (ada 2 bilangan di antara 1 s/d n yg hilang dari array itu).



Soal pertama mungkin udah sering nongol di Google, tapi yg kedua mungkin lebih jarang.