N-th Number Divisible by One of Three

Medium

You are given four positive integers n, p, q and r. Consider, in increasing order, every positive integer divisible by at least one of p, q or r. Return the n-th number of this sequence (counting from 1). The answer is guaranteed not to exceed 2·10⁹. Walking through the numbers one by one is too slow, since the answer can be huge.

Example 1

n=5, p=3, q=4, r=6 → 9

The matching numbers are 3, 4, 6, 8, 9, 12, … and the fifth is 9.

Example 2

n=4, p=5, q=5, r=7 → 14

Divisors may repeat. The matches are 5, 7, 10, 14, … so the fourth is 14.

Example 3

n=6, p=2, q=9, r=10 → 10

Constraints

1 ≤ n, p, q, r ≤ 10⁹
p · q · r ≤ 10¹⁸
The answer does not exceed 2·10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Binary Search Combinatorics Number Theory

Similar problems

K-th Postage With One Stamp Type Hard Pair GCDs by Sorted Position Hard Numbers for Two Groups Medium Shave Primes Into Order Medium Divisor Chains Hard

Input

n=5, p=3, q=4, r=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 124 tests on the server, hidden ones included.