Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Máme zadané N. ako ohraničenie maximálneho možného čísla.
Môžeme začať od 3 do N a spočítavať čísla, ktoré sú deliteľné 3 a 5 (použijeme operáciu modulo). Tu nám nemusí vyjsť správny výsledok, pretože niektoré čísla sú započítané 2x. Tie čísla sú deliteľné 15, lebo algoritmus ich započíta aj pri porovnávaní deliteľnosti 3 a 5. Čísla deliteľné 15 musíme z celkového výsledku odpočítať.
Toto riešenie nie je tiež efektívne. Ak by bolo číslo N príliš vysoké a porovnávali by sme postupne deliteľnosť každého čísla, prekročili by sme časový limit na úlohu.
Existuje trik, ako rýchlo spočítať čísla, ktoré sa medzi sebou líšia medzi sebou len vždy o rovnakú hodnotu (v našom prípade o 3, 5 a 15).
Pomôže nám vzťah. Stačí mať najmenšie a najväčšie číslo v postupnosti čísel líšiacich sa o hodnotu d a ich počet n. Ich počet získame, keď vydelíme maximálne číslo v postupnosti číslom d.
Napríklad, ak je N = 20. Najväčšie číslo menšie ako 20, ktoré je deliteľné 3 je 18. Najmenšie je 3. Ich počet dostaneme rovnicou n = 18/3 = 6. Ich súčet bude:
![\[\frac{n(min + max)}{2} = \frac{6 \times (3 + 18)}{2} = 63\]](http://pidanic.com/wp-content/ql-cache/quicklatex.com-702a90b214abc0144a5782c782f7c4c4_l3.png "Rendered by QuickLaTeX.com")
.
Podobne si vypočítame súčty pre čísla deliteľné 5 a 15.
Rovnica pre vyriešenie úlohy:
![\[Sum = {Sum}_3 + {Sum}_5 - {Sum}_{15}\]](http://pidanic.com/wp-content/ql-cache/quicklatex.com-ee3d34cdf334219c0b8a811211906e41_l3.png "Rendered by QuickLaTeX.com")
Vytvoril som riešenie v týchto programovacích jazykoch:
Všetky riešenia sú dostupné aj na mojom GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
import java.util.Scanner; public class Multiples { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { long number = Long.parseLong(scanner.nextLine()); long result = sumOfMultiples(number); System.out.println(result); } scanner.close(); } // http://en.wikipedia.org/wiki/Arithmetic_progression private static long sumOfMultiples(long number) { long result = 0; if (number > 3) { long min = 3; long count = (number - 1) / 3; long max = number - 1; while (max % 3 != 0) { max--; } long tempResult = count * (min + max) / 2; result += tempResult; } if (number > 5) { long min = 5; long count = (number - 1) / 5; long max = number - 1; while (max % 5 != 0) { max--; } long tempResult = count * (min + max) / 2; result += tempResult; } if (number > 15) { long min = 15; long count = (number - 1) / 15; long max = number - 1; while (max % 15 != 0) { max--; } long tempResult = count * (min + max) / 2; result -= tempResult; } return result; } } |