How should I practice Sum of Smallest Non-Divisors?

Start by reading the full statement, solve the visible examples, then compare the pattern against related The D.E. Shaw Group phone screen problems in FastPrep.

Is Sum of Smallest Non-Divisors associated with The D.E. Shaw Group?

FastPrep tags this as a The D.E. Shaw Group phone screen coding practice problem when the problem catalog has that company and stage context.

Sum of Smallest Non-Divisors

The D.E. Shaw Group● MediumFULLTIMEPHONE SCREEN

Problem statement

For a positive integer x, let f(x) be the smallest positive integer k with x % k != 0. In other words, f(x) is the smallest positive integer that does not divide x. For example, f(1) = 2, f(6) = 4, and f(12) = 5.

Given an integer n, return the sum of f(x) over every integer x with 1 <= x <= n - 1. This is the same range as range(1, n) in Python, so n itself is not included. When n = 1, the range is empty and the answer is 0.

Return the exact sum. It is less than 3 * 10^15, so it fits in a 64-bit integer.

Function

sumSmallestNonDivisors(n: long) → long

Examples

Example 1

n = 7return = 16

The sum covers x = 1 through 6.

f(1) = 2, f(3) = 2, and f(5) = 2, because 2 does not divide an odd number.
f(2) = 3 and f(4) = 3, because 1 and 2 divide them but 3 does not.
f(6) = 4, because 1, 2, and 3 divide 6 but 4 does not.

The sum is 2 + 3 + 2 + 3 + 2 + 4 = 16.

Example 2

n = 13return = 33

The values for x = 1 through 6 add up to 16, as in Example 1. For x = 7 through 12, the values are 2, 3, 2, 3, 2, 5: f(12) = 5 because 1, 2, 3, and 4 divide 12 but 5 does not. The sum is 16 + 17 = 33.

Example 3

n = 1return = 0

There is no integer x with 1 <= x <= 0, so the sum is empty and the answer is 0.

Constraints

1 <= n <= 10^15

More The D.E. Shaw Group problems

See The D.E. Shaw Group hiring insights