Horje
Minimize division by 2 to make an Array strictly increasing

Given an array nums[] of size N, the task is to find the minimum number of operations required to modify the array such that array elements are in strictly increasing order (A[i] < A[i+1]) where in each operation we can choose any element and perform nums[i] = [ nums[i] / 2] (where [x] represents the floor value of integer x).

Examples:

Input nums[] = {2, 8, 7, 5}
Output: 4
Explanation: Perform 1 operation on nums[0], 2 operations on nums[1], and 1 operation on nums[2]. 

Input: nums[] = {5, 3, 2, 1}
Output: -1
Explanation:  It is impossible to obtain a strictly increasing sequence. Thus, return -1

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

Idea is to start iterating from the second last element in the reverse direction and find if nums[i] ? nums[i+1] at any point we now can try to make nums[i] smaller than nums[i+1] by dividing the nums[i] by 2 until nums[i] becomes smaller than nums[i+1] and simultaneously can increase the count to keep record of operation done so far.

Follow the steps mentioned below to implement the idea:

  • Initialize count = 0.
  • Start iterating from the second last element in the reverse direction
  • If nums[i+1] = 0, break and return -1 as this is not possible to make the array strictly increasing.
  • As long as nums[i] ? nums[i+1] divide nums[i] by 2 and increment count.
  • Return count as the required answer.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for calculating minimum operation
// to convert array into strictly increasing
int minOperation(vector<int>& nums, int n)
{
    bool flag = false;
    int count = 0;
 
    // Iterating from second last element
    // in reverse direction
    for (int i = n - 2; i >= 0; i--) {
 
        // If any element becomes 0 other than
        // that of index 0, final result will be -1
        if (nums[i + 1] == 0) {
            flag = true;
            break;
        }
 
        // As long as the current element is greater
        // than or equal to the next element,
        // divide it by 2 and increase the count
        while (nums[i] >= nums[i + 1]) {
 
            count++;
            nums[i] /= 2;
        }
    }
 
    // If 0 found in array other than that of
    // index 0, return -1
    if (flag == true)
        return -1;
 
    // Return count of operation.
    return count;
}
 
// Driver code
int main()
{
    vector<int> nums = { 2, 8, 7, 5 };
    int N = nums.size();
 
    // Function call
    cout << minOperation(nums, N);
 
    return 0;
}

Java

// Java code to implement the approach
import java.util.*;
import java.io.*;
 
class GFG {
  // Function for calculating minimum operation
  // to convert array into strictly increasing
  public static int minOperation(int[] nums, int n) {
    int flag = 0;
    int count = 0;
 
    // Iterating from second last element
    // in reverse direction
    for(int i = n-2; i >= 0; i--) {
 
      // If any element becomes 0 other than
      // that of index 0, final result will be -1
      if(nums[i+1] == 0) {
        flag = 1;
        break;
      }
 
 
      // As long as the current element is greater
      // than or equal to the next element,
      // divide it by 2 and increase the count
      while(nums[i] >= nums[i+1]) {
        count++;
        nums[i] /= 2;
      }
    }
 
    // If 0 found in array other than that of
    // index 0, return -1
    if (flag == 1)
      return -1;
 
    // Return count of operation.
    return count;
  }
 
  // Driver code
  public static void main(String[] args) {
    int[] nums = {2, 8, 7, 5};
    int N = nums.length;
 
    // Function call
    System.out.println(minOperation(nums, N));
  }
}

C#

// C# code to implement the approach
using System;
using System.Collections.Generic;
 
class GFG {
    // Function for calculating minimum operation
    // to convert array into strictly increasing
    static int minOperation(List<int> nums, int n)
    {
        bool flag = false;
        int count = 0;
 
        // Iterating from second last element
        // in reverse direction
        for (int i = n - 2; i >= 0; i--) {
 
            // If any element becomes 0 other than
            // that of index 0, final result will be -1
            if (nums[i + 1] == 0) {
                flag = true;
                break;
            }
 
            // As long as the current element is greater
            // than or equal to the next element,
            // divide it by 2 and increase the count
            while (nums[i] >= nums[i + 1]) {
 
                count++;
                nums[i] /= 2;
            }
        }
 
        // If 0 found in array other than that of
        // index 0, return -1
        if (flag == true)
            return -1;
 
        // Return count of operation.
        return count;
    }
 
    // Driver code
    public static void Main()
    {
        List<int> nums = new List<int>{ 2, 8, 7, 5 };
        int N = nums.Count;
 
        // Function call
        Console.Write(minOperation(nums, N));
    }
}

Javascript

// Javascript code to implement the approach
 
// Function for calculating minimum operation
// to convert array into strictly increasing
function minOperation(nums, n)
{
    let flag = false
    let count = 0
 
    // Iterating from second last element
    // in reverse direction
    for (let i = n - 2; i >= 0; i--) {
 
        // If any element becomes 0 other than
        // that of index 0, final result will be -1
        if (nums[i + 1] == 0) {
            flag = true
            break
        }
 
        // As long as the current element is greater
        // than or equal to the next element,
        // divide it by 2 and increase the count
        while (nums[i] >= nums[i + 1]) {
 
            count++
            nums[i] /= 2
        }
    }
 
    // If 0 found in array other than that of
    // index 0, return -1
    if (flag == true)
        return -1
 
    // Return count of operation.
    return count
}
 
// Driver code
 
    let nums = [2, 8, 7, 5 ]
    let N = nums.length
 
    // Function call
    console.log(minOperation(nums, N))
     
    // This code is contributed by poojaagarwal2.

Python3

# Function for calculating minimum operation
# to convert array into strictly increasing
def minOperation(nums):
    n = len(nums)
    flag = False
    count = 0
 
    # Iterating from second last element
    # in reverse direction
    for i in range(n-2, -1, -1):
 
        # If any element becomes 0 other than
        # that of index 0, final result will be -1
        if nums[i + 1] == 0:
            flag = True
            break
 
        # As long as the current element is greater
        # than or equal to the next element,
        # divide it by 2 and increase the count
        while nums[i] >= nums[i + 1]:
            count += 1
            nums[i] = nums[i] // 2
 
    # If 0 found in array other than that of
    # index 0, return -1
    if flag:
        return -1
 
    # Return count of operation.
    return count
 
# Driver code
if __name__ == '__main__':
    nums = [2, 8, 7, 5]
 
    # Function call
    print(minOperation(nums))

Output

4

Time Complexity: O(N)
Auxiliary Space: O(1)

Related Articles:


 


Reffered: https://www.geeksforgeeks.org

DSA

Related
Maximize coins that can be collected by moving on given coordinates Maximize coins that can be collected by moving on given coordinates
Make Array sum even using minimum operations Make Array sum even using minimum operations
Maximum length of sequence formed from cost N Maximum length of sequence formed from cost N
Greedy Best first search algorithm Greedy Best first search algorithm
Hash Table vs Trie Hash Table vs Trie

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje