Minimize insertions required to make ratio of maximum and minimum of all pairs of adjacent array elements at most K
Given an array arr[] and an integer K ( > 1), the task is to find the minimum number of insertions required such that the ratio of the maximum and minimum of all pairs of adjacent elements in the array reduces to at most K.
Examples:
Input : arr[] = { 2, 10, 25, 21 }, K = 2
Output: 3
Explanation:
Following insertions makes the array satisfy the required conditions {2, 4, 7, 10, 17, 25, 21}.Input : arr[] = {2, 4, 1}, K = 2
Output: 1
Approach: The idea is to use greedily. Follow the steps to solve the problem :
- Traverse the array arr[].
- Initialize a variable, say ans, to store the number of insertions required.
- Iterate over the range [0, N – 2] and perform the following steps:
- Calculate min(arr[i], arr[i + 1]) and max(arr[i], arr[i + 1]) and store it in variables, say a and b.
- If (b > K * a): Update a = K * a and increment ans by 1.
- Print the value of ans as 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 count the minimum // number of insertions required int mininsert( int arr[], int K, int N) { // Stores the number of // insertions required int ans = 0; // Traverse the array for ( int i = 0; i < N - 1; i++) { // Store the minimum array element int a = min(arr[i], arr[i + 1]); // Store the maximum array element int b = max(arr[i], arr[i + 1]); // Checking condition while (K * a < b) { a *= K; // Increase current count ans++; } } // Return the count of insertions return ans; } // Driver Code int main() { int arr[] = { 2, 10, 25, 21 }; int K = 2; int N = sizeof (arr) / sizeof (arr[0]); cout << mininsert(arr, K, N); return 0; } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to count the minimum // number of insertions required static int mininsert( int arr[], int K, int N) { // Stores the number of // insertions required int ans = 0 ; // Traverse the array for ( int i = 0 ; i < N - 1 ; i++) { // Store the minimum array element int a = Math.min(arr[i], arr[i + 1 ]); // Store the maximum array element int b = Math.max(arr[i], arr[i + 1 ]); // Checking condition while (K * a < b) { a *= K; // Increase current count ans++; } } // Return the count of insertions return ans; } // Driver Code public static void main(String[] args) { int arr[] = { 2 , 10 , 25 , 21 }; int K = 2 ; int N = arr.length; System.out.print(mininsert(arr, K, N)); } } // This code is contributed by shikhasingrajput |
Python3
# Python3 program for the above approach # Function to count the minimum # number of insertions required def mininsert(arr, K, N) : # Stores the number of # insertions required ans = 0 # Traverse the array for i in range (N - 1 ): # Store the minimum array element a = min (arr[i], arr[i + 1 ]) # Store the maximum array element b = max (arr[i], arr[i + 1 ]) # Checking condition while (K * a < b) : a * = K # Increase current count ans + = 1 # Return the count of insertions return ans # Driver Code arr = [ 2 , 10 , 25 , 21 ] K = 2 N = len (arr) print (mininsert(arr, K, N)) # This code is contributed by susmitakundugoaldanga. |
C#
// C# program for the above approach using System; class GFG{ // Function to count the minimum // number of insertions required static int mininsert( int [] arr, int K, int N) { // Stores the number of // insertions required int ans = 0; // Traverse the array for ( int i = 0; i < N - 1; i++) { // Store the minimum array element int a = Math.Min(arr[i], arr[i + 1]); // Store the maximum array element int b = Math.Max(arr[i], arr[i + 1]); // Checking condition while (K * a < b) { a *= K; // Increase current count ans++; } } // Return the count of insertions return ans; } // Driver Code public static void Main( string [] args) { int [] arr = { 2, 10, 25, 21 }; int K = 2; int N = arr.Length; Console.Write(mininsert(arr, K, N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript program to implement // the above approach // Function to count the minimum // number of insertions required function mininsert(arr , K , N) { // Stores the number of // insertions required var ans = 0; // Traverse the array for (i = 0; i < N - 1; i++) { // Store the minimum array element var a = Math.min(arr[i], arr[i + 1]); // Store the maximum array element var b = Math.max(arr[i], arr[i + 1]); // Checking condition while (K * a < b) { a *= K; // Increase current count ans++; } } // Return the count of insertions return ans; } // Driver Code var arr = [ 2, 10, 25, 21 ]; var K = 2; var N = arr.length; document.write(mininsert(arr, K, N)); // This code contributed by umadevi9616 </script> |
Output:
3
Time Complexity: O(N * log(M)), where M is the largest element in the array.
Auxiliary Space: O(1)