Maximum number of times Array can be reduced in half when its all elements are even
Given an array arr, the task is to perform operations on the array when all elements in the array are even. In one operation, replace each integer X in the array by X/2. Find maximum possible number of operations that you can perform.
Examples:
Input: arr[] = {8, 12, 40}
Output: 2
Explanation: Initially, {8, 12, 40} are present in array. Since all those integers are even,
you can perform the operation. After the operation is performed once, array becomes
{4, 6, 20}. Since all those integers are again even, we can perform the operation again.
After the operation is performed twice, array becomes {2, 3, 10}. Now, there is an odd
number “3” in the array, so no operation can be performed anymore.
Thus, you can perform the operation at most twice.Input: arr[] = {5, 6, 8, 10}
Output: 0
Explanation: Since there is an odd number 5 in the initial array, we cant perform the
operation even once.
Approach: Given problem can be solved by making some simple observations:
- If all integers in the array at present are even, then we divide all the numbers by 2.
- Thus, the problem reduces to finding the number of times an element arr[i] can be divided by 2. Let it be times[i] . The answer is the minimum value of times[i] for all i.
- Instead of using an additional array times[], we can update the answer at each stage by simply keeping a variable, this reduces the space complexity to O(1) as we are not using any additional space.
Below is the implementation of the above idea.
C++
// C++ code implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to return the number // of operations possible int arrayDivisionByTwo( int arr[], int n) { // counter to store the number of times the // current element is divisible by 2 int cnt = 0; // variable to store the final answer int ans = INT_MAX; for ( int i = 0; i < n; i++) { // Initialize the counter to zero // for each element cnt = 0; while (arr[i] % 2 == 0) { // update the counter till the // number is divisible by 2 arr[i] = arr[i] / 2; cnt++; } // update the answer as // the minimum of all the counts ans = min(ans, cnt); } return ans; } // Driver code int main() { int arr[] = { 8, 12, 40 }; int n = sizeof (arr) / sizeof (arr[0]); cout << arrayDivisionByTwo(arr, n); return 0; } |
Java
// Java code implementation for the above approach import java.util.*; class GFG { // Function to return the number // of operations possible static int arrayDivisionByTwo( int arr[], int n) { // counter to store the number of times the // current element is divisible by 2 int cnt = 0 ; // variable to store the final answer int ans = Integer.MAX_VALUE; for ( int i = 0 ; i < n; i++) { // Initialize the counter to zero // for each element cnt = 0 ; while (arr[i] % 2 == 0 ) { // update the counter till the // number is divisible by 2 arr[i] = arr[i] / 2 ; cnt++; } // update the answer as // the minimum of all the counts ans = Math.min(ans, cnt); } return ans; } // Driver code public static void main(String[] args) { int arr[] = { 8 , 12 , 40 }; int n = arr.length; System.out.print(arrayDivisionByTwo(arr, n)); } } // This code is contributed by Princi Singh |
Python3
# Python 3 code implementation for the above approach import sys # Function to return the number # of operations possible def arrayDivisionByTwo(arr, n): # counter to store the number of times the # current element is divisible by 2 cnt = 0 # variable to store the final answer ans = sys.maxsize for i in range (n): # Initialize the counter to zero # for each element cnt = 0 while (arr[i] % 2 = = 0 ): # update the counter till the # number is divisible by 2 arr[i] = arr[i] / / 2 cnt + = 1 # update the answer as # the minimum of all the counts ans = min (ans, cnt) return ans # Driver code if __name__ = = '__main__' : arr = [ 8 , 12 , 40 ] n = len (arr) print (arrayDivisionByTwo(arr, n)) # This code is contributed by ipg2016107. |
C#
// C# code implementation for the above approach using System; class GFG{ // Function to return the number // of operations possible static int arrayDivisionByTwo( int []arr, int n) { // counter to store the number of times the // current element is divisible by 2 int cnt = 0; // variable to store the final answer int ans = Int32.MaxValue; for ( int i = 0; i < n; i++) { // Initialize the counter to zero // for each element cnt = 0; while (arr[i] % 2 == 0) { // update the counter till the // number is divisible by 2 arr[i] = arr[i] / 2; cnt++; } // update the answer as // the minimum of all the counts ans = Math.Min(ans, cnt); } return ans; } // Driver code public static void Main(String[] args) { int []arr = { 8, 12, 40 }; int n = arr.Length; Console.Write(arrayDivisionByTwo(arr, n)); } } // This code is contributed by shivanisinghss2110 |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to return the number // of operations possible function arrayDivisionByTwo(arr, n) { // counter to store the number of times the // current element is divisible by 2 let cnt = 0; // variable to store the final answer let ans = Number.MAX_VALUE; for (let i = 0; i < n; i++) { // Initialize the counter to zero // for each element cnt = 0; while (arr[i] % 2 == 0) { // update the counter till the // number is divisible by 2 arr[i] = Math.floor(arr[i] / 2); cnt++; } // update the answer as // the minimum of all the counts ans = Math.min(ans, cnt); } return ans; } // Driver code let arr = [8, 12, 40]; let n = arr.length; document.write(arrayDivisionByTwo(arr, n)); //This code is contributed by Potta Lokesh </script> |
2
Time Complexity: O(32 * n)
Space Complexity: O(1)
Contact Us