ho fatto tutto il possibile per le mie competenze, fare 100/100 va al di fuori. ho scritto il seguente codice:
semplicemente ho usato la formula (n/1 + n/2 + ... + n/n) e ho anche ottimizzato mettendo un if che controlla quando la divisione riporta 1, essendo che in quel caso da li fino a n/n il risultato sarà sempre 1. Però:
La soluzione ottima non è O(\log N). Un buon punto di partenza per trovarla è considerare che 1 non è l’unico risultato che appare molte volte in \{\lfloor\frac{n}{1}\rfloor,\lfloor\frac{n}{2}\rfloor,\ldots \lfloor\frac{n}{n}\rfloor\}.
eh si ci avevo pensato, ma come faccio a capire un numero quante volte restituisce 2 o 3 in tutte le divisioni \{[\frac{n}{1}], [\frac{n}{2}], ...[\frac{n}{n}]\}.
Puoi pensarla così, supponi che stai cercando quanti x esistono tali che \lfloor \frac{n}{x} \rfloor = k, e quindi formi l’insieme D_k = \{x | \lfloor \frac{n}{x} \rfloor = k\}, quello che puoi “sfruttare” a tuo vantaggio è che tale insieme corrisponde all’insieme \{min(D_k), min(D_k) + 1, \dots, max(D_k) - 1, max(D_k)\}, ciò significa che, per ogni k, se tu fossi in grando di stabilire il minimo e il massimo valore di x per il quale vale \lfloor \frac{n}{x} \rfloor = k allora puoi ottenere D_k (o meglio ancora |D_k|). Per rendere l’idea se n = 100.000 e sono interessato a k = 2, se scopro che min(D_k) = 33.334, max(D_k) = 50.000 allora posso anche sapere che |D_k| = 50.000 - 33.334 + 1
