Given an array arr[] consisting of N positive integers, the task is to find the minimum steps required to make the given array of integers into a sequence of powers of 2 by the following operations:
- Reorder the given array. It doesn’t count as a step.
- For each step, select any index i from the array and change arr[i] to arr[i] ? 1 or arr[i] + 1.
A sequence is called power sequence of 2, if for every ith index (0 ?i ? N ? 1),
arr[i] = 2i , where N is length of the given array.
Examples:
Input: arr[] = { 1, 8, 2, 10, 6 }
Output: 8
Explanation:
Reorder the array arr[] to { 1, 2, 6, 8, 10 }
Step 1: Decrement arr[2] to 5
Step 2: Decrement arr[2] to 4
Step 3 – 8: Increment arr[4] by 1. Final value of arr[4] becomes 16.
Therefore, arr[] = {1, 2, 4, 8, 16}
Hence, the minimum number of steps required to obtain the power sequence of 2 is 8.Input: arr[] = { 1, 3, 4 }
Output: 1
Approach: To solve the given problem, the idea is to sort the array in ascending order and for every ith index of the sorted array, calculate the absolute difference between arr[i] and 2i. The sum of the absolute differences gives us the required answer.
Below is the implementation of the above approach:
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 2int 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 Codeint 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 approachimport 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)); }} |
Python3
# Python 3 program for the above approach# Function to calculate the minimum# steps required to convert given# array into a power sequence of 2def 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 Codearr = [1, 8, 2, 10, 6]n = len(arr)print(minsteps(arr, n)) |
C#
// C# Program to the above approachusing 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)); }} |
Javascript
<script>// Javascript program to implement// the above approach// Function to calculate the minimum// steps required to convert given// array into a power sequence of 2function 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 Codevar arr = [ 1, 8, 2, 10, 6 ];var n = arr.length;document.write( minsteps(arr, n));// This code is contributed by noob2000.</script> |
8
Time Complexity: O(NlogN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!