Given an array, arr[] of size N. Find the minimum number of elements we need to insert between array elements such that the maximum element from two adjacent elements is not more than twice bigger than the minimum element i.e., max(arr[i], arr[i+1]) ? 2 * min(arr[i], arr[i+1]) where 0 ? i < N – 1.

Examples:

Input: N = 5, A[] = {1, 2, 3, 4, 3}
Output: 0
Explanation:

• Element 1 whose value is 1 and neighbour value is 2. max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is true, no need to insert anything
• Element 2 whose value is 2 and neighbour value is 3. max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is true, no need to insert anything
• Element 3 whose value is 3 and neighbour value is 4. max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is true, no need to insert anything
• Element 4 whose value is 4 and neighbour value is 3. max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is true, no need to insert anything

Therefore, the minimum number of insertions required is 0.

Input: N = 4, A[] = {4, 2, 10, 1}
Output: 5
Explanation:

• Element 1 whose value is 4 and neighbour value is 2,   max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is true, no need to insert anything.
• Element 2 whose value is 2 and neighbour value is 10, max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is not true, so we can insert 5, 3.
• Element 3 whose value is 10 and neighbour value is 1,   max(arr[i], arr[i+1]) ? 2 * (min(arr[i], arr[i+1])) is not true, so we can insert 5, 3, 2

Therefore, the minimum number of insertions required is 0 + 2 + 3 = 5.

Approach: This problem can be solved based on the following idea:

Iterate from the start of the array till the second last element. Inside the loop check, if the Ratio of the maximum element and minimum element between adjacent elements is fulfilling the ideal condition (i.e. ? 2), till it is not true try to insert a maximum value that we can insert (i.e. ceil(maxEle/2), ceil will found upper bound if the result is in decimal) and we will also increase the counter by 1 every time.

Follow the steps below to solve the problem:

• Initialize the count = 0, to count the minimum number of insertions required.
• Iterate over the array A[].
• If maxEle / minEle > 2, update the maxEle = ceil(maxEle / 2) and increment the count of insertion.
• After iterating, return the count.

Below is the implementation of the above approach:

5

Time Complexity: O(N*log(H)), where N is the length of the array and H is the value of the maximum array element
Auxiliary Space: O(1)

Related Articles:

• Introduction to Arrays – Data Structures and Algorithms Tutorials