Mínimo dividir por 2 operaciones requeridas para hacer que GCD sea impar para una array dada

Dada una array arr[] de N enteros positivos, la tarea es encontrar el número mínimo de operaciones requeridas para hacer que el GCD del elemento de la array sea impar de modo que en cada operación un elemento de la array se pueda dividir por 2 .

Ejemplos:

Entrada: arr[] = {4, 6}
Salida: 1
Explicación:
A continuación se muestran las operaciones realizadas:
Operación 1: Dividir el elemento del arreglo arr[0](= 4) por 2 modifica el arreglo a {2, 6}.
Operación 2: dividir el elemento de array arr[0](= 2) por 2 modifica la array a {1, 6}.
Después de las operaciones anteriores, el GCD de los elementos de la array es 1, que es impar. Por lo tanto, el número mínimo de operaciones requeridas es 2.

Entrada: arr[] = {2, 4, 1}
Salida: 0

Enfoque: El problema dado se puede resolver con base en la observación al encontrar el conteo de potencias de 2 para cada elemento de array y la potencia mínima de 2 (digamos C ) dará las operaciones mínimas porque después de dividir ese elemento por 2 ^C el elemento se convierte en impar y eso da como resultado que el GCD de la array sea impar .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of operations to make the GCD of
// the array odd
int minimumOperations(int arr[], int N)
{
    // Stores the minimum operations
    // required
    int mini = INT_MAX;
 
    for (int i = 0; i < N; i++) {
 
        // Stores the powers of two for
        // the current array element
        int count = 0;
 
        // Dividing by 2
        while (arr[i] % 2 == 0) {
            arr[i] = arr[i] / 2;
 
            // Increment the count
            count++;
        }
 
        // Update the minimum operation
        // required
        if (mini > count) {
            mini = count;
        }
    }
 
    // Return the result required
    return mini;
}
 
// Driver Code
int main()
{
    int arr[] = { 4, 6 };
    int N = sizeof(arr) / sizeof(arr[0]);
 
    cout << minimumOperations(arr, N);
 
    return 0;
}

// Java program for the above approach
class GFG{
 
// Function to find the minimum number
// of operations to make the GCD of
// the array odd
public static int minimumOperations(int arr[], int N)
{
   
    // Stores the minimum operations
    // required
    int mini = Integer.MAX_VALUE;
 
    for (int i = 0; i < N; i++) {
 
        // Stores the powers of two for
        // the current array element
        int count = 0;
 
        // Dividing by 2
        while (arr[i] % 2 == 0) {
            arr[i] = arr[i] / 2;
 
            // Increment the count
            count++;
        }
 
        // Update the minimum operation
        // required
        if (mini > count) {
            mini = count;
        }
    }
 
    // Return the result required
    return mini;
}
 
// Driver Code
public static void  main(String args[])
{
    int arr[] = { 4, 6 };
    int N = arr.length;
 
    System.out.println(minimumOperations(arr, N));
 
}
}
 
// This code is contributed by saurabh_jaiswal.

# python program for the above approach
INT_MAX = 2147483647
 
# Function to find the minimum number
# of operations to make the GCD of
# the array odd
def minimumOperations(arr, N):
 
    # Stores the minimum operations
    # required
    mini = INT_MAX
 
    for i in range(0, N):
 
        # Stores the powers of two for
        # the current array element
        count = 0
 
        # Dividing by 2
        while (arr[i] % 2 == 0):
            arr[i] = arr[i] // 2
 
            # Increment the count
            count += 1
 
        # Update the minimum operation
        # required
        if (mini > count):
            mini = count
 
    # Return the result required
    return mini
 
# Driver Code
if __name__ == "__main__":
 
    arr = [4, 6]
    N = len(arr)
 
    print(minimumOperations(arr, N))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG {
 
    // Function to find the minimum number
    // of operations to make the GCD of
    // the array odd
    public static int minimumOperations(int[] arr, int N)
    {
 
        // Stores the minimum operations
        // required
        int mini = Int32.MaxValue;
 
        for (int i = 0; i < N; i++) {
 
            // Stores the powers of two for
            // the current array element
            int count = 0;
 
            // Dividing by 2
            while (arr[i] % 2 == 0) {
                arr[i] = arr[i] / 2;
 
                // Increment the count
                count++;
            }
 
            // Update the minimum operation
            // required
            if (mini > count) {
                mini = count;
            }
        }
 
        // Return the result required
        return mini;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int[] arr = { 4, 6 };
        int N = arr.Length;
 
        Console.WriteLine(minimumOperations(arr, N));
    }
}
 
// This code is contributed by ukasp.

<script>
// Javascript program for the above approach
 
// Function to find the minimum number
// of operations to make the GCD of
// the array odd
function minimumOperations(arr, N)
{
 
  // Stores the minimum operations
  // required
  let mini = Number.MAX_SAFE_INTEGER;
 
  for (let i = 0; i < N; i++)
  {
   
    // Stores the powers of two for
    // the current array element
    let count = 0;
 
    // Dividing by 2
    while (arr[i] % 2 == 0) {
      arr[i] = Math.floor(arr[i] / 2);
 
      // Increment the count
      count++;
    }
 
    // Update the minimum operation
    // required
    if (mini > count) {
      mini = count;
    }
  }
 
  // Return the result required
  return mini;
}
 
// Driver Code
 
let arr = [4, 6];
let N = arr.length;
 
document.write(minimumOperations(arr, N));
 
// This code is contributed by saurabh_jaiswal.
</script>

1

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)