0904EasyMath

Marks Struck Off by Three, Five or Seven

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tally sheet is marked 1 through n.

A mark is struck off when it divides evenly by 3, by 5 or by 7. Return the total of the marks struck off.

Examples

Example 1

Input: n = 143
Output: 5523

Every multiple of 3, 5 or 7 up to 143 is struck off, and their total comes to this once the overlaps have been settled.

Example 2

Input: n = 15
Output: 81

The marks struck off are 3, 5, 6, 7, 9, 10, 12, 14 and 15, which total 81. The mark 15 divides by both 3 and 5 yet is counted once.

Example 3

Input: n = 2
Output: 0

Neither mark divides by 3, 5 or 7.

Constraints

1 <= n <= 10^3

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def sum_of_multiples(n: int) -> int:

Java

public int sumOfMultiples(int n)

The intended approach

Time O(1): six closed-form sums, whatever n is.Space O(1).

The marks divisible by some `d` are `d`, `2d`, `3d` and so on, and there are `n / d` of them rounded down, so their total is `d` times the sum of the whole numbers up to that count, which is a closed form and needs no loop. Adding the three totals for 3, 5 and 7 double counts anything divisible by two of them, so take back the totals for 15, 21 and 35. That in turn removes the marks divisible by all three once too often, so add the total for 105 back. Six closed-form sums settle the whole tally.

Pythonentry point: sum_of_multiples

def sum_of_multiples(n):
    def struck(step):
        count = n // step
        return step * count * (count + 1) // 2

    return (struck(3) + struck(5) + struck(7)
            - struck(15) - struck(21) - struck(35)
            + struck(105))

The obvious version

Walk every mark from 1 to n, test it against each of the three divisors, and add it in if any of them divides it. Linear in n and it never worries about double counting.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_sum_of_multiples(n):
    total = 0
    for mark in range(1, n + 1):
        if mark % 3 == 0 or mark % 5 == 0 or mark % 7 == 0:
            total += mark
    return total

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in