Dada una array , arr[] que consta de N enteros positivos, la tarea es hacer que todos los elementos de la array sean iguales a 1 realizando las siguientes operaciones un número mínimo de veces:
- Incrementa el valor de todos los elementos de un subarreglo por cualquier número entero positivo.
- Si todos los elementos de la array son pares, divida todos los elementos de la array por 2 .
Imprime el conteo de operaciones mínimas requeridas.
Ejemplos:
Entrada: arr[] = { 3, 1, 2, 4 }
Salida: 3
Explicación:
Incrementar arr[0] en 1, arr[1] en 3 y arr[2] en 2 modifica arr[] a { 4, 4 , 4, 4 }.
Dividir todos los elementos de la array por 2 modifica arr[] a { 2, 2, 2, 2 }.
Dividir todos los elementos de la array por 2 modifica arr[] a { 1, 1, 1, 1 }.
Por lo tanto, la salida requerida es 3.Entrada: arr[] = { 2, 4 }
Salida: 3
Explicación:
Dividir todos los elementos de la array por 2 modifica arr[] a { 1, 2 }.
Incrementar el valor de arr[0] en 1 modifica arr[] a { 2, 2 }.
Dividir todos los elementos de la array por 2 modifica arr[] a { 1, 2 }.
Por lo tanto, la salida requerida es 3.
Enfoque: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:
- Encuentre el elemento más grande de la array , digamos, Max .
- Si todos los elementos de la array son iguales y también en forma de potencia de 2 , imprima log 2 (Max) .
- De lo contrario, iguale todos los elementos de la array a la potencia más cercana de 2 que sea mayor o igual a Max e imprima log 2 (Max) + 1.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sapu10lm39 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA