smallest-missing-non-negative-integer-after-operations

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 0-indexed integer array <code>nums</code> and an integer <code>value</code>.

In one operation, you can add or subtract <code>value</code> from any element of <code>nums</code>.

<ul>
	<li>For example, if <code>nums = [1,2,3]</code> and <code>value = 2</code>, you can choose to subtract <code>value</code> from <code>nums[0]</code> to make <code>nums = [-1,2,3]</code>.</li>
</ul>

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

<ul>
	<li>For example, the MEX of <code>[-1,2,3]</code> is <code>0</code> while the MEX of <code>[1,0,3]</code> is <code>2</code>.</li>
</ul>

Return the maximum MEX of <code>nums</code> after applying the mentioned operation any number of times.

&nbsp;
Example 1:

<pre>
Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: One can achieve this result by applying the following operations:
- Add value to nums[1] twice to make nums = [1,0,7,13,6,8]
- Subtract value from nums[2] once to make nums = [1,0,2,13,6,8]
- Subtract value from nums[3] twice to make nums = [1,0,2,3,6,8]
The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.
</pre>

Example 2:

<pre>
Input: nums = [1,-10,7,13,6,8], value = 7
Output: 2
Explanation: One can achieve this result by applying the following operation:
- subtract value from nums[2] once to make nums = [1,-10,0,13,6,8]
The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length, value &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>

findSmallestInteger

Smallest Missing Non-negative Integer After Operations

First Missing Positive

first-missing-positive

缺失的第一个正数

Greedy

Array

Hash Table

Math

给你一个下标从 0 开始的整数数组 <code>nums</code> 和一个整数 <code>value</code> 。

在一步操作中，你可以对 <code>nums</code> 中的任一元素加上或减去 <code>value</code> 。

<ul>
	<li>例如，如果 <code>nums = [1,2,3]</code> 且 <code>value = 2</code> ，你可以选择 <code>nums[0]</code> 减去 <code>value</code> ，得到 <code>nums = [-1,2,3]</code> 。</li>
</ul>

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

<ul>
	<li>例如，<code>[-1,2,3]</code> 的 MEX 是 <code>0</code> ，而 <code>[1,0,3]</code> 的 MEX 是 <code>2</code> 。</li>
</ul>

返回在执行上述操作 任意次 后，<code>nums</code> 的最大 MEX 。

&nbsp;

示例 1：

<pre>输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。
</pre>

示例 2：

<pre>输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length, value &lt;= 105</code></li>
	<li><code>-109 &lt;= nums[i] &lt;= 109</code></li>
</ul>