Maximum number of multiplication by 3 or division by 2 operations possible on an array

0 0 4 minutes read

Given an array arr[] consisting of N positive integers, the task is to find the maximum number of times each array element can either be multiplied by M or divided by K.
Note: At least one element needs to be divided by M and K respectively in each operation.

Examples:

Input: arr[] = {5, 2, 4}, M = 3, K = 2
Output: 3
Explanation:
One possible way to perform the operations is:

Multiply arr[1] and arr[2] by 3, and divide arr[3] by 2. The array modifies to {15, 6, 2}.

Multiply arr[1] and arr[3] by 3, divide arr[2] by 2. The array modifies to {45, 3, 6}.

Multiply arr[1] by 3 and arr[2] by 3 and divide arr[3] by 2. The array modifies to {135, 9, 3}.

No further operation is possible since no element is divisible by 2.

Therefore, the maximum number of operations possible is 3.

Input: arr[] = {3, 5, 7}
Output: 0

Approach: This problem can be solved by observing that, successively dividing an array element by 2, the count of even elements will decrease after some constant number of steps. So, to maximize the number of turns, only one even element is divided by 2, and all others are multiplied by 3 in a single step. Follow the steps below to solve the problem:

Initialize a variable, say, Count as 0, that will store the count of power of 2 in every element of the array.
Iterate in the range [0, N-1] using the variable i and perform the following steps:
- Iterate until the arr[i] is divisible by 2, then increment the Count by 1 and divide arr[i] by 2.
After performing the above steps, print the value of Count as the answer.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count maximum number
// of multiplication by 3 or division
// by 2 operations that can be performed
int maximumTurns(int arr[], int N)
{
 
    // Stores the maximum number
    // of operations possible
    int Count = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // Iterate until arr[i] is even
        while (arr[i] % 2 == 0) {
 
            // Increment count by 1
            Count++;
 
            // Update arr[i]
            arr[i] = arr[i] / 2;
        }
    }
 
    // Return the value of
    // Count as the answer
    return Count;
}
 
// Driver Code
int main()
{
 
    // Given Input
    int arr[] = { 5, 2, 4 };
    int M = 3, K = 2;
    int N = sizeof(arr) / sizeof(arr[0]);
 
    // Function Call
    cout << maximumTurns(arr, N);
 
    return 0;
}

Java

// Java program for the above approach
public class GFG
{
 
    // Function to count maximum number
    // of multiplication by 3 or division
    // by 2 operations that can be performed
    static int maximumTurns(int arr[], int N)
    {
 
        // Stores the maximum number
        // of operations possible
        int Count = 0;
 
        // Traverse the array arr[]
        for (int i = 0; i < N; i++) {
 
            // Iterate until arr[i] is even
            while (arr[i] % 2 == 0) {
 
                // Increment count by 1
                Count++;
 
                // Update arr[i]
                arr[i] = arr[i] / 2;
            }
        }
 
        // Return the value of
        // Count as the answer
        return Count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
       
        // Given Input
        // Given Input
        int arr[] = { 5, 2, 4 };
        int M = 3, K = 2;
        int N = arr.length;
 
        // Function Call
        System.out.println(maximumTurns(arr, N));
    }
}
 
// This code is contributed by abhinavjain194

Python3

# Python3 program for the above approach
 
# Function to count maximum number
# of multiplication by 3 or division
# by 2 operations that can be performed
def maximumTurns(arr, N):
     
    # Stores the maximum number
    # of operations possible
    Count = 0
     
    # Traverse the array arr[]
    for i in range(0, N):
         
        # Iterate until arr[i] is even
        while (arr[i] % 2 == 0):
             
            # Increment count by 1
            Count += 1
             
            # Update arr[i]
            arr[i] = arr[i] // 2
 
    # Return the value of
    # Count as the answer
    return Count
 
# Driver code
 
# Given Input
arr = [ 5, 2, 4 ]
M = 3
K = 2
N = len(arr)
 
# Function Call
print(maximumTurns(arr, N))
 
# This code is contributed by amreshkumar3

C#

// C# program for the above approach
 
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to count maximum number
// of multiplication by 3 or division
// by 2 operations that can be performed
static int maximumTurns(int []arr, int N)
{
 
    // Stores the maximum number
    // of operations possible
    int Count = 0;
 
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
 
        // Iterate until arr[i] is even
        while (arr[i] % 2 == 0) {
 
            // Increment count by 1
            Count++;
 
            // Update arr[i]
            arr[i] = arr[i] / 2;
        }
    }
 
    // Return the value of
    // Count as the answer
    return Count;
}
 
// Driver Code
public static void Main()
{
 
    // Given Input
    int []arr = { 5, 2, 4 };
    int N = arr.Length;
 
    // Function Call
    Console.Write(maximumTurns(arr, N));
}
}
 
// This code is contributed by ipg2016107.

Javascript

<script>
 
// JavaScript program for the above approach
 
// Function to count maximum number
// of multiplication by 3 or division
// by 2 operations that can be performed
function maximumTurns(arr, N) {
 
    // Stores the maximum number
    // of operations possible
    let Count = 0;
 
    // Traverse the array arr[]
    for (let i = 0; i < N; i++) {
 
        // Iterate until arr[i] is even
        while (arr[i] % 2 == 0) {
 
            // Increment count by 1
            Count++;
 
            // Update arr[i]
            arr[i] = Math.floor(arr[i] / 2);
        }
    }
 
    // Return the value of
    // Count as the answer
    return Count;
}
 
// Driver Code
 
 
// Given Input
let arr = [5, 2, 4];
let M = 3, K = 2;
let N = arr.length;
 
// Function Call
document.write(maximumTurns(arr, N));
 
</script>

Output:

Time complexity: O(N*log(M)) where M is the maximum value of the array.
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 zambiatek!