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 increasingint 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 codeint 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 approachimport 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 approachusing 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 increasingfunction 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 increasingdef 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 codeif __name__ == '__main__': nums = [2, 8, 7, 5] # Function call print(minOperation(nums)) |
Output
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
