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 notbool 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 1int 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 Codeint main(){ int arr[] = { 2, 4 }; int N = sizeof(arr) / sizeof(arr[0]); cout << minCntOperations(arr, N);} |
Java
// Java program to implement// the above approachimport 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 approachimport math# Function to check if all array# elements are equal or notdef 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 1def 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 Codeif __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 approachusing 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> |
Output:
3
Time Complexity: O(N)
Auxiliary Space: O(1)
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!