将给定数组重新排列为 2 的幂序列所需的最小步数
给定一个由 N 正整数组成的数组arr【】，任务是通过以下操作找到将给定的整数数组变成 2 的次幂序列所需的最小步骤:
- 给定数组重新排序。不算一步。
- 对于每一步，从数组中选择任意索引 i ，并将arr【I】更改为arr【I】1或arr【I】+1。
一个序列被称为 2、 if 的幂序列，对于每个 i 第索引(0≤I≤N-1)、 arr【I】= 2I，其中 N 是给定数组的长度。
*示例:*
*输入:* arr[] = { 1，8，2，10，6 } 输出: 8 解释: 将数组 arr[]重新排序为{ 1，2，6，8，10 } 步骤 1:将 arr[2]递减为 5 步骤 2:将 arr[2]递减为 4 步骤 3–8:将 arr[4]递增 1。arr[4]的最终值变为 16。 因此，arr[] = {1，2，4，8，16} 因此，获得 2 的幂序列所需的最小步数是 8。
*输入:* arr[] = { 1，3，4 } T3】输出: 1
*方法:*为了解决给定的问题，思路是按照升序对数组进行排序，对于排序后的数组的每个 i 第个索引，计算arr【I】和 2 i 之间的绝对差值。绝对差异的总和给了我们所需的答案。
下面是上述方法的实现:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate the minimum
// steps required to convert given
// array into a power sequence of 2
int minsteps(int arr[], int n)
{
// Sort the array in
// ascending order
sort(arr, arr + n);
int ans = 0;
// Calculate the absolute difference
// between arr[i] and 2^i for each index
for (int i = 0; i < n; i++) {
ans += abs(arr[i] - pow(2, i));
}
// Return the answer
return ans;
}
// Driver Code
int main()
{
int arr[] = { 1, 8, 2, 10, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << minsteps(arr, n) << endl;
return 0;
}
Java 语言(一种计算机语言，尤用于创建网站)
// Java Program to implement
// the above approach
import java.util.*;
import java.lang.Math;
class GFG {
// Function to calculate the minimum
// steps required to convert given
// array into a power sequence of 2
static int minsteps(int arr[], int n)
{
// Sort the array in ascending order
Arrays.sort(arr);
int ans = 0;
// Calculate the absolute difference
// between arr[i] and 2^i for each index
for (int i = 0; i < n; i++) {
ans += Math.abs(arr[i] - Math.pow(2, i));
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 1, 8, 2, 10, 6 };
int n = arr.length;
System.out.println(minsteps(arr, n));
}
}
Python 3
# Python 3 program for the above approach
# Function to calculate the minimum
# steps required to convert given
# array into a power sequence of 2
def minsteps(arr, n):
# Sort the array in ascending order
arr.sort()
ans = 0
for i in range(n):
ans += abs(arr[i]-pow(2, i))
return ans
# Driver Code
arr = [1, 8, 2, 10, 6]
n = len(arr)
print(minsteps(arr, n))
C#
// C# Program to the above approach
using System;
class GFG {
// Function to calculate the minimum
// steps required to convert given
// array into a power sequence of 2
static int minsteps(int[] arr, int n)
{
// Sort the array in ascending order
Array.Sort(arr);
int ans = 0;
// Calculate the absolute difference
// between arr[i] and 2^i for each index
for (int i = 0; i < n; i++) {
ans += Math.Abs(arr[i]
- (int)(Math.Pow(2, i)));
}
return ans;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 8, 2, 10, 6 };
int n = arr.Length;
Console.WriteLine(minsteps(arr, n));
}
}
java 描述语言
<script>
// Javascript program to implement
// the above approach
// Function to calculate the minimum
// steps required to convert given
// array into a power sequence of 2
function minsteps(arr, n)
{
// Sort the array in
// ascending order
arr.sort((a,b)=>a-b)
var ans = 0;
// Calculate the absolute difference
// between arr[i] and 2^i for each index
for (var i = 0; i < n; i++) {
ans += Math.abs(arr[i] - Math.pow(2, i));
}
// Return the answer
return ans;
}
// Driver Code
var arr = [ 1, 8, 2, 10, 6 ];
var n = arr.length;
document.write( minsteps(arr, n));
// This code is contributed by noob2000.
</script>
**Output:
8**
*时间复杂度: O(NlogN) 辅助空间: O(1)***
版权属于：月萌API www.moonapi.com，转载请注明出处
