Elakadtam egy HackerRanks feladatban, hol lehet a hibám? (bármely C szerű nyelvben)

Nem én voltam a 7-es válaszoló, de megvédeném. Valószínűleg akkor még nem olvasta azt a kommentet, hogy az értékkészlet 1 és 99 közé esik. (12 perccel az ő kommentje előtt volt, akár lehet, hogy addig írta a válaszát mert pl valami közbejött neki)

Nyilván 2-100 darab számra ami 1-99 közé esik konstans időben megoldható a feladat:)

Úgy írjatok O(n)-es megoldást, hogy a számok méretére nincs kitétel (vagy mondjuk maximum 1024 bites számok, erre a jelenlegi gépeken nem tudtok elég memóriát foglalni).

#22 senki nem mondta, hogy O(1) space-ben megoldható a feladat.

O(n)-ben pedig simán megoldható a számok értékhatárától függetlenül (egy bizonyos értékhatár felett már nyilván HashMap-et használva).

#21, #22 te a fogalmakkal sem vagy tisztában, úgy tűnik.

"Nyilván 2-100 darab számra ami 1-99 közé esik konstans időben megoldható a feladat:)"

Igen? Oldd már meg akkor konstans időben, tehát O(1)-ben.

És aztán publikálhatod is egyből, mert senki más nem tudja a világon rajtad kívül :)

"Úgy írjatok O(n)-es megoldást, hogy a számok méretére nincs kitétel (vagy mondjuk maximum 1024 bites számok, erre a jelenlegi gépeken nem tudtok elég memóriát foglalni)."

Ezzel az a gáz, hogy adott függvénynek, a változók számosságától függően, akár több Ordója is lehet, de ilyenkor is a legkisebbet kell venni.

A hetes viszont expressis verbis kizárta O(n)-t.

"Igen? Oldd már meg akkor konstans időben, tehát O(1)-ben."

A megadott feltételekkel (kevesebb mint) 100^200 bemenet lehetséges. (azért 100, mert ha pl 3 számot vizsgálunk, vehetjük úgy, hogy 8,3,5,0,0,0,0....)

Fogsz egy 100^200 méretű memóriát (oké, ez nagy, de korlátos és nem függ a bemenettől) és feltöltöd az előre kiszámolt értékekkel a következő képen:

A bemenetből (tomb) generálsz egy indexet:

index = 0;

ciklus i = 1-200:

ha tomb hossza >= i

index = index + tomb[i]

index = idnex * 256; // vagy 100, ahogy tetszik...

ciklus vége

Ez a ciklus konstans 200 lépés, nem függ a bemenet hosszától...

A memóriádnak az adott elemén az ennek megfelelő "válasznak" kell lennie előre kiszámolva. (Monduk beégetve a kódban)

Majd az algoritmusod csak kiszámolja ezt az indexet (konstans futásidő...) és megnézi mi van ott a memóriában..

Oké, lehet sokkal hatékonyabban is, de nem ezt a kérdés.

Nem kell zseninek lenni ahhoz hogy belásd hogy korlátos bemenet esetén az adott korlátnak megfelelő időn belül lefutó algoritmust lehet írni.

Nyilván írhattam volna a ciklust a bement hosszáig, de nem akartam hogy megzavarjon, még azt hinnéd, hogy függ a bemenet hosszától a futásidő.

"A HashMap-ekkel az a baj, hogy ha direkt úgy válogatják ki a számokat (nyilván nem az 1-99-es intervallumbelieket, hanem bármilyen "elég nagyot"), hogy sok ütközés legyen, akkor nem fog lineáris időben lefutni. Erre csak az exponenciális (értékkészlet méretének) méretű tárhely lenne a megoldás."

Semmi baj nincs a HashMap-ekkel.

Ha mondjuk 32 bites integer hasheket használunk (nyilván ez nyelvtől is függ) és ennél nagyobb az értékkészlet, akkor egyszerűen csak több HashMap-et használunk.

Adott érték megfelelő HashMap-hez rendelése nyilván O(1) művelet, tehát a komplexitást abszolút nem befolyásolja.

#28 írj már egy példát, mert elképesztő baromságnak tűnik, amit írtál, de lehet csak én értem félre.

(Mármint konkrét példát arra, hogy az általad leírt logikával megoldod a feladatot)