count-distinct-numbers-on-board

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a positive integer <code>n</code>, that is initially placed on a board. Every day, for <code>109</code> days, you perform the following procedure:

<ul>
	<li>For each number <code>x</code> present on the board, find all numbers <code>1 &lt;= i &lt;= n</code> such that <code>x % i == 1</code>.</li>
	<li>Then, place those numbers on the board.</li>
</ul>

Return the number of distinct integers present on the board after <code>109</code> days have elapsed.

Note:

<ul>
	<li>Once a number is placed on the board, it will remain on it until the end.</li>
	<li><code>%</code>&nbsp;stands&nbsp;for the modulo operation. For example,&nbsp;<code>14 % 3</code> is <code>2</code>.</li>
</ul>

&nbsp;
Example 1:

<pre>
Input: n = 5
Output: 4
Explanation: Initially, 5 is present on the board. 
The next day, 2 and 4 will be added since 5 % 2 == 1 and 5 % 4 == 1. 
After that day, 3 will be added to the board because 4 % 3 == 1. 
At the end of a billion days, the distinct numbers on the board will be 2, 3, 4, and 5. 
</pre>

Example 2:

<pre>
Input: n = 3
Output: 2
Explanation: 
Since 3 % 2 == 1, 2 will be added to the board. 
After a billion days, the only two distinct numbers on the board are 2 and 3. 
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>

distinctIntegers

Count Distinct Numbers on Board

Count of Matches in Tournament

count-of-matches-in-tournament

比赛中的配对次数

Array

Hash Table

Math

Simulation

给你一个正整数 <code>n</code> ，开始时，它放在桌面上。在 <code>109</code> 天内，每天都要执行下述步骤：

<ul>
	<li>对于出现在桌面上的每个数字 <code>x</code> ，找出符合 <code>1 &lt;= i &lt;= n</code> 且满足 <code>x % i == 1</code> 的所有数字 <code>i</code> 。</li>
	<li>然后，将这些数字放在桌面上。</li>
</ul>

返回在 <code>109</code> 天之后，出现在桌面上的 不同 整数的数目。

注意：

<ul>
	<li>一旦数字放在桌面上，则会一直保留直到结束。</li>
	<li><code>%</code> 表示取余运算。例如，<code>14 % 3</code> 等于 <code>2</code> 。</li>
</ul>

&nbsp;

示例 1：

<pre>
输入：n = 5
输出：4
解释：最开始，5 在桌面上。 
第二天，2 和 4 也出现在桌面上，因为 5 % 2 == 1 且 5 % 4 == 1 。 
再过一天 3 也出现在桌面上，因为 4 % 3 == 1 。 
在十亿天结束时，桌面上的不同数字有 2 、3 、4 、5 。
</pre>

示例 2：

<pre>
输入：n = 3 
输出：2
解释： 
因为 3 % 2 == 1 ，2 也出现在桌面上。 
在十亿天结束时，桌面上的不同数字只有两个：2 和 3 。 
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
</ul>