Given an array consisting of N integers, the task is to find the integer K which requires the minimum number of moves to convert the given array to a sequence of powers of K, i.e. {K0, K1, K2, ……., KN – 1}. In each move, increase or decrease an array element by one.
Examples:
Input: arr[] = {1, 2, 3}
Output: 2
Explanation: By incrementing arr[2] by 1 modifies to {1, 2, 4} which is equal to {20, 21, 22}. Therefore, K = 2.Input: arr[] = {1, 9, 27}
Output: 5
Explanation: Modifying array to {1, 5, 25} requires minimum number of moves. Therefore, K = 5.
Approach: The idea is to check for all the numbers starting from 1 till the power of a number crosses the maximum value i.e. 1010 (assumed). Follow the steps below to solve the problem:
- Check for all the numbers from 1 to x until the value of xN – 1 < max_element of array + move needed to convert in the power of 1.
- Count the moves needed to make an array in the power of that element.
- If the move needed is minimum than the previous value then update the value of K and min moves.
- Print the value of K.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define ll long long// Function to find the value of K such// that it takes minimum number of moves// to convert the array in its powerll findMinCostInteger(vector<ll>& a){ // Size of the array int n = a.size(); // Finding the sum of the array ll sum = accumulate(a.begin(), a.end(), 0); ll K = 0, minmove = LLONG_MAX; // Find K for which the count // of moves will become minimum for (int i = 1;; ++i) { ll power = 1, count = 0; for (ll j = 0; j < n; ++j) { count += abs(a[j] - power); if (j != n - 1) power = power * (ll)i; // If exceeds maximum value if (power >= 1e10) break; } if (power >= (1e10) || power > (ll)(sum - n) + a[n - 1]) break; // Update minimum moves if (minmove > count) { minmove = count; K = i; } } // Print K corresponds to minimum // number of moves cout << K;}// Driver Codeint main(){ // Given vector vector<ll> a = { 1, 9, 27 }; // Function Call findMinCostInteger(a); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find the value of K such// that it takes minimum number of moves// to convert the array in its powerstatic void findMinCostInteger(int a[], int n){ // Finding the sum of the array int sum = 0; for(int i = 0; i < n; i++) sum += a[i]; int K = 0, minmove = Integer.MAX_VALUE; // Find K for which the count // of moves will become minimum for(int i = 1;; ++i) { int power = 1, count = 0; for(int j = 0; j < n; ++j) { count += Math.abs(a[j] - power); if (j != n - 1) power = power * i; // If exceeds maximum value if (power >= 1e10) break; } if (power >= (1e10) || power > (sum - n) + a[n - 1]) break; // Update minimum moves if (minmove > count) { minmove = count; K = i; } } // Print K corresponds to minimum // number of moves System.out.println(K);}// Driver Codepublic static void main(String args[]){ // Given vector int []a = { 1, 9, 27 }; // Function Call findMinCostInteger(a, 3);}}// This code is contributed by bgangwar59 |
Python3
# Python3 program for the above approachimport sys# Function to find the value of K such# that it takes minimum number of moves# to convert the array in its powerdef findMinCostInteger(a): # Size of the array n = len(a) # Finding the sum of the array sm = sum(a) K = 0 minmove = sys.maxsize # Find K for which the count # of moves will become minimum i = 1 while(1): power = 1 count = 0 for j in range(n): count += abs(a[j] - power) if (j != n - 1): power = power * i # If exceeds maximum value if (power >= 1e10): break if (power >= (1e10) or power > (sm - n) + a[n - 1]): break # Update minimum moves if (minmove > count): minmove = count K = i i += 1 # Print K corresponds to minimum # number of moves print(K)# Driver Codeif __name__ == '__main__': # Given vector a = [ 1, 9, 27 ] # Function Call findMinCostInteger(a) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the// above approachusing System;class GFG{ // Function to find the value // of K such that it takes // minimum number of moves// to convert the array in // its powerstatic void findMinCostint(int []a, int n){ // Finding the sum of the array int sum = 0; for(int i = 0; i < n; i++) sum += a[i]; int K = 0, minmove = int.MaxValue; // Find K for which the count // of moves will become minimum for(int i = 1;; ++i) { int power = 1, count = 0; for(int j = 0; j < n; ++j) { count += Math.Abs(a[j] - power); if (j != n - 1) power = power * i; // If exceeds maximum value if (power >= 1e10) break; } if (power >= (1e10) || power > (sum - n) + a[n - 1]) break; // Update minimum moves if (minmove > count) { minmove = count; K = i; } } // Print K corresponds to // minimum number of moves Console.WriteLine(K);}// Driver Codepublic static void Main(String []args){ // Given vector int []a = {1, 9, 27}; // Function Call findMinCostint(a, 3);}}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Function to find the value of K such// that it takes minimum number of moves// to convert the array in its powerfunction findMinCostLeteger(a, n){ // Finding the sum of the array let sum = 0; for(let i = 0; i < n; i++) sum += a[i]; let K = 0, minmove = Number.MAX_VALUE; // Find K for which the count // of moves will become minimum for(let i = 1;; ++i) { let power = 1, count = 0; for(let j = 0; j < n; ++j) { count += Math.abs(a[j] - power); if (j != n - 1) power = power * i; // If exceeds maximum value if (power >= 1e10) break; } if (power >= (1e10) || power > (sum - n) + a[n - 1]) break; // Update minimum moves if (minmove > count) { minmove = count; K = i; } } // Print K corresponds to minimum // number of moves document.write(K);}// Driver Code// Given vectorlet a = [ 1, 9, 27 ];// Function CallfindMinCostLeteger(a, 3);// This code is contributed by souravghosh0416</script> |
Output
5
Time Complexity: O(N * max(x))
Auxiliary Space: O(1)
