minimize-deviation-in-array

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 an array <code>nums</code> of <code>n</code> positive integers.

You can perform two types of operations on any element of the array any number of times:

<ul>
	<li>If the element is even, divide it by <code>2</code>.

	<ul>
		<li>For example, if the array is <code>[1,2,3,4]</code>, then you can do this operation on the last element, and the array will be <code>[1,2,3,2].</code></li>
	</ul>
	</li>
	<li>If the element is odd, multiply it by <code>2</code>.
	<ul>
		<li>For example, if the array is <code>[1,2,3,4]</code>, then you can do this operation on the first element, and the array will be <code>[2,2,3,4].</code></li>
	</ul>
	</li>
</ul>

The deviation of the array is the maximum difference between any two elements in the array.

Return the minimum deviation the array can have after performing some number of operations.

&nbsp;
Example 1:

<pre>
Input: nums = [1,2,3,4]
Output: 1
Explanation: You can transform the array to [1,2,3,2], then to [2,2,3,2], then the deviation will be 3 - 2 = 1.
</pre>

Example 2:

<pre>
Input: nums = [4,1,5,20,3]
Output: 3
Explanation: You can transform the array after two operations to [4,2,5,5,3], then the deviation will be 5 - 2 = 3.
</pre>

Example 3:

<pre>
Input: nums = [2,10,8]
Output: 3
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>

minimumDeviation

Minimize Deviation in Array

Greedy

Array

Ordered Set

Heap (Priority Queue)

给你一个由 <code>n</code> 个正整数组成的数组 <code>nums</code> 。

你可以对数组的任意元素执行任意次数的两类操作：

<ul>
	<li>如果元素是 偶数 ，除以 <code>2</code>

	<ul>
		<li>例如，如果数组是 <code>[1,2,3,4]</code> ，那么你可以对最后一个元素执行此操作，使其变成 <code>[1,2,3,2]</code></li>
	</ul>
	</li>
	<li>如果元素是 奇数 ，乘上 <code>2</code>
	<ul>
		<li>例如，如果数组是 <code>[1,2,3,4]</code> ，那么你可以对第一个元素执行此操作，使其变成 <code>[2,2,3,4]</code></li>
	</ul>
	</li>
</ul>

数组的 偏移量 是数组中任意两个元素之间的 最大差值 。

返回数组在执行某些操作之后可以拥有的 最小偏移量 。

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,4]
输出：1
解释：你可以将数组转换为 [1,2,3,2]，然后转换成 [2,2,3,2]，偏移量是 3 - 2 = 1
</pre>

示例 2：

<pre>
输入：nums = [4,1,5,20,3]
输出：3
解释：两次操作后，你可以将数组转换为 [4,2,5,5,3]，偏移量是 5 - 2 = 3
</pre>

示例 3：

<pre>
输入：nums = [2,10,8]
输出：3
</pre>

&nbsp;

提示：

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>2 &lt;= n &lt;= 5 * 104</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>