Einfach 0 gelöst 0% Erfolgsquote

Sum of Multiples

Add values below a limit divisible by any supplied factor.

Das lernst du

  • Test a number against several factors
  • Avoid counting a value twice
  • Accumulate a total below a limit

Problem

Übersetzung anzeigen

Consider positive integers strictly below limit. Include a value if it is divisible by at least one nonzero factor. Count each included value once even if several factors divide it. Ignore zero factors. Factors [3, 5] give the familiar multiples-of-3-or-5 task.

Implement sum_of_multiples(limit, factors).

Input

limit: The exclusive upper bound.

factors: The factors whose multiples are eligible.

Output

Return the sum of distinct eligible positive integers.

Einschränkungen

0 ≤ limit ≤ 100,000. There may be 0 through 20 factors, each between 0 and 100,000. Duplicate factors are allowed.

Beispiele

Beispiel 1
Eingabe:
limit = 12
factors = [3, 5]

Erwartete Ausgabe:
expected = 33
Eingabe:
long long limit = 12;
std::vector<long long> factors = {3, 5};

Erwartete Ausgabe:
long long expected = 33;
Eingabe:
long limit = 12;
long[] factors = new long[] {3, 5};

Erwartete Ausgabe:
long expected = 33;

Erläuterung

The included values are 3, 5, 6, 9, and 10. Their sum is 33.

Beispiel 2
Eingabe:
limit = 10
factors = [2, 4]

Erwartete Ausgabe:
expected = 20
Eingabe:
long long limit = 10;
std::vector<long long> factors = {2, 4};

Erwartete Ausgabe:
long long expected = 20;
Eingabe:
long limit = 10;
long[] factors = new long[] {2, 4};

Erwartete Ausgabe:
long expected = 20;

Erläuterung

Include 2, 4, 6, and 8. Values 4 and 8 are counted once despite matching both factors.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Only values divisible by at least one usable factor should contribute once.

Hinweis 2

Use inclusion-exclusion to combine overlapping factor multiples without double counting.

Hinweis 3

Ignore zero factors and duplicates before doing any arithmetic.

Erwartete Komplexität

O(2^m) time, O(1) extra space

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.