Pasos mínimos necesarios para reorganizar la array dada a una secuencia de potencia de 2

Dada una array arr[] que consta de N enteros positivos , la tarea es encontrar los pasos mínimos necesarios para convertir la array dada de enteros en una secuencia de potencias de 2 mediante las siguientes operaciones:

• Reordenar la array dada. No cuenta como un paso.
• Para cada paso, seleccione cualquier índice i de la array y cambie arr[i] a arr[i] − 1 o arr[i] + 1 .

 Una secuencia se llama secuencia de potencia de 2, si para cada i ^-ésimo índice (0 ≤i ≤ N − 1) , 
arr[i] = 2 ⁱ , donde N es la longitud de la array dada.

Ejemplos:

Entrada: arr[] = { 1, 8, 2, 10, 6 }
Salida: 8
Explicación: 
Reordenar la array arr[] a { 1, 2, 6, 8, 10 }
Paso 1: Decrementar arr[2] a 5
Paso 2: Disminuya arr[2] a 4
Paso 3 – 8: Incremente arr[4] en 1. El valor final de arr[4] se convierte en 16.
Por lo tanto, arr[] = {1, 2, 4, 8, 16}
Por lo tanto, el número mínimo de pasos necesarios para obtener la secuencia de potencia de 2 es 8.

Entrada: arr[] = { 1, 3, 4 }
Salida: 1

Enfoque: para resolver el problema dado, la idea es ordenar la array en orden ascendente  y, para cada i ^-ésimo índice de la array ordenada, calcular la diferencia absoluta entre arr[i]   y 2 ⁱ . La suma de las diferencias absolutas nos da la respuesta requerida.

A continuación se muestra la implementación del enfoque anterior:

// 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 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 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# 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));
    }
}

<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>

8

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)