All problems

Foghorn Minutes

Medium · math

A harbour has three foghorns. The first sounds every a minutes, the second every b minutes and the third every c minutes. Each one sounds at minutes a, 2a, 3a, ... (and likewise for b and c), counting from the moment the fog rolls in at minute 0.

A minute is noisy if at least one foghorn sounds during it. A minute in which two or three foghorns sound at once is still just one noisy minute.

Return how many of the minutes 1, 2, ..., n are noisy.

Examples

Example 1

Input: a = 2, b = 3, c = 5, n = 10

Output: 8

The noisy minutes are 2, 3, 4, 5, 6, 8, 9 and 10. Minutes 1 and 7 are quiet.

Example 2

Input: a = 4, b = 4, c = 4, n = 20

Output: 5

All three foghorns sound together at 4, 8, 12, 16 and 20, which is five noisy minutes.

Example 3

Input: a = 7, b = 11, c = 13, n = 5

Output: 0

The fog lifts before any foghorn has sounded.

Constraints