Count Distinct Numbers on Board — LeetCode 2549 Python Solution

The problem

You are given a positive integer n, that is initially placed on a board. Every day, for 109 days, you perform the following procedure: For each number x present on the board, find all numbers 1 <= i <= n such that x % i == 1.

Example

Input

n = 5

Output

4

Explanation

Initially, 5 is present on the board.

Python solution

class Solution:
    def distinctIntegers(self, n: int) -> int:
        return max(1, n - 1)

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 2549. Count Distinct Numbers on Board is filed here because LeetCode tags it Math, which is the vocabulary this hub collects.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems