Given an array, arr[] consisting of N positive integers, the task is to make all array elements equal to 1 by performing the following operations minimum number of times:
- Increment the value of all elements of a subarray by any positive integers.
- If all the array elements are even then divide all the array elements by 2.
Print the count of minimum operations required.
Examples:
Input: arr[] = { 3, 1, 2, 4 }
Output: 3
Explanation:
Incrementing arr[0] by 1, arr[1] by 3 and arr[2] by 2 modifies arr[] to { 4, 4, 4, 4 }.
Dividing all the array elements by 2 modifies arr[] to { 2, 2, 2, 2 }.
Dividing all the array elements by 2 modifies arr[] to { 1, 1, 1, 1 }.
Therefore, the required output is 3.Input: arr[] = { 2, 4 }
Output: 3
Explanation:
Dividing all the array elements by 2 modifies arr[] to { 1, 2 }.
Incrementing the value of arr[0] by 1 modifies arr[] to { 2, 2 }.
Dividing all the array elements by 2 modifies arr[] to { 1, 2 }.
Therefore, the required output is 3.
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Find the largest element of the array say, Max.
- If all the array elements are equal and also in the form of power of 2, then print log2(Max).
- Otherwise, make all the array elements equal to the closest power of 2 which is greater than or equal to Max and print log2(Max) + 1.
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 check if all array // elements are equal or not bool CheckAllEqual( int arr[], int N) { // Traverse the array for ( int i = 1; i < N; i++) { // If all array elements // are not equal if (arr[0] != arr[i]) { return false ; } } return true ; } // Function to find minimum count of operation // to make all the array elements equal to 1 int minCntOperations( int arr[], int N) { // Stores largest element of the array int Max = *max_element(arr, arr + N); // Check if a number is a power of 2 or not bool isPower2 = !(Max && (Max & (Max - 1))); // If Max is a power of 2 and all // array elements are equal if (isPower2 && CheckAllEqual(arr, N)) { return log2(Max); } else { return ceil (log2(Max)) + 1; } } // Driver Code int main() { int arr[] = { 2, 4 }; int N = sizeof (arr) / sizeof (arr[0]); cout << minCntOperations(arr, N); } |
Java
// Java program to implement // the above approach import java.io.*; import java.util.*; class GFG { // Function to check if all array // elements are equal or not static boolean CheckAllEqual( int arr[], int N) { // Traverse the array for ( int i = 1 ; i < N; i++) { // If all array elements // are not equal if (arr[ 0 ] != arr[i]) { return false ; } } return true ; } // Function to find minimum count of operation // to make all the array elements equal to 1 static int minCntOperations( int arr[], int N) { // Stores largest element of the array int Max = Arrays.stream(arr).max().getAsInt(); // Check if a number is a power of 2 or not boolean isPower2; if (( int )(Math.ceil((Math.log(N) / Math.log(N)))) == ( int )(Math.floor(((Math.log(N) / Math.log( 2 )))))) { isPower2 = true ; } else { isPower2 = false ; } // If Max is a power of 2 and all // array elements are equal if (isPower2 && CheckAllEqual(arr, N)) { return ( int )(Math.log(Max) / Math.log( 2 )); } else { return ( int )Math.ceil(Math.log(Max) / Math.log( 2 )) + 1 ; } } // Driver Code public static void main(String[] args) { int [] arr = new int [] { 2 , 4 }; int N = arr.length; System.out.println(minCntOperations(arr, N)); } } // This code is contributed by Dharanendra L V |
Python3
# Python 3 program to implement # the above approach import math # Function to check if all array # elements are equal or not def CheckAllEqual(arr, N): # Traverse the array for i in range ( 1 , N): # If all array elements # are not equal if (arr[ 0 ] ! = arr[i]): return False return True # Function to find minimum count of operation # to make all the array elements equal to 1 def minCntOperations(arr, N): # Stores largest element of the array Max = max (arr) # Check if a number is a power of 2 or not isPower2 = not ( Max and ( Max & ( Max - 1 ))) # If Max is a power of 2 and all # array elements are equal if (isPower2 and CheckAllEqual(arr, N)): return log2( Max ) else : return math.ceil(math.log2( Max )) + 1 # Driver Code if __name__ = = "__main__" : arr = [ 2 , 4 ] N = len (arr) print (minCntOperations(arr, N)) # This code is contributed by chitranayal. |
C#
// C# program to implement // the above approach using System; using System.Linq; class GFG { // Function to check if all array // elements are equal or not static bool CheckAllEqual( int [] arr, int N) { // Traverse the array for ( int i = 1; i < N; i++) { // If all array elements // are not equal if (arr[0] != arr[i]) { return false ; } } return true ; } // Function to find minimum count of operation // to make all the array elements equal to 1 static int minCntOperations( int [] arr, int N) { // Stores largest element of the array int Max = arr.Max(); // Check if a number is a power of 2 or not bool isPower2; if (( int )(Math.Ceiling((Math.Log(N) / Math.Log(N)))) == ( int )(Math.Floor(((Math.Log(N) / Math.Log(2)))))) { isPower2 = true ; } else { isPower2 = false ; } // If Max is a power of 2 and all // array elements are equal if (isPower2 && CheckAllEqual(arr, N)) { return ( int )(Math.Log(Max) / Math.Log(2)); } else { return ( int )Math.Ceiling(Math.Log(Max) / Math.Log(2)) + 1; } } // Driver Code static public void Main() { int [] arr = new int [] { 2, 4 }; int N = arr.Length; Console.WriteLine(minCntOperations(arr, N)); } } // This code is contributed by Dharanendra L V |
Javascript
<script> // javascript program to implement // the above approach // Function to check if all array // elements are equal or not function CheckAllEqual(arr, N) { // Traverse the array for (i = 1; i < N; i++) { // If all array elements // are not equal if (arr[0] != arr[i]) { return false ; } } return true ; } // Function to find minimum count of operation // to make all the array elements equal to 1 function minCntOperations(arr, N) { // Stores largest element of the array var Max =Math.max.apply(Math,arr); // Check if a number is a power of 2 or not var isPower2; if (parseInt( (Math.ceil((Math.log(N) / Math.log(N))))) == parseInt( (Math.floor(((Math.log(N) / Math.log(2))))))) { isPower2 = true ; } else { isPower2 = false ; } // If Max is a power of 2 and all // array elements are equal if (isPower2 && CheckAllEqual(arr, N)) { return parseInt( (Math.log(Max) / Math.log(2))); } else { return parseInt( Math.ceil(Math.log(Max) / Math.log(2))) + 1; } } // Driver Code var arr = [ 2, 4 ]; var N = arr.length; document.write(minCntOperations(arr, N)); // This code is contributed by Rajput-Ji </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!