Considere una array con n elementos y el valor de todos los elementos es cero. Podemos realizar las siguientes operaciones en la array.
- Operaciones incrementales: elija 1 elemento de la array e incremente su valor en 1.
- Operación de duplicación: duplica los valores de todos los elementos de la array.
Se nos da la array deseada target[] que contiene n elementos. Calcule y devuelva el número más pequeño posible de las operaciones necesarias para cambiar la array de ceros a la array deseada.
Ejemplos:
C++
/* C++ program to count minimum number of operations
to get the given target array */
#include <bits/stdc++.h>
using namespace std;
// Returns count of minimum operations to convert a
// zero array to target array with increment and
// doubling operations.
// This function computes count by doing reverse
// steps, i.e., convert target to zero array.
int countMinOperations(unsigned int target[], int n)
{
// Initialize result (Count of minimum moves)
int result = 0;
// Keep looping while all elements of target
// don't become 0.
while (1)
{
// To store count of zeroes in current
// target array
int zero_count = 0;
int i; // To find first odd element
for (i=0; i<n; i++)
{
// If odd number found
if (target[i] & 1)
break;
// If 0, then increment zero_count
else if (target[i] == 0)
zero_count++;
}
// All numbers are 0
if (zero_count == n)
return result;
// All numbers are even
if (i == n)
{
// Divide the whole array by 2
// and increment result
for (int j=0; j<n; j++)
target[j] = target[j]/2;
result++;
}
// Make all odd numbers even by subtracting
// one and increment result.
for (int j=i; j<n; j++)
{
if (target[j] & 1)
{
target[j]--;
result++;
}
}
}
}
/* Driver program to test above functions*/
int main()
{
unsigned int arr[] = {16, 16, 16};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Minimum number of steps required to "
"get the given target array is "
<< countMinOperations(arr, n);
return 0;
}
Java
/* Java program to count minimum number of operations
to get the given arr array */
class Test
{
static int arr[] = new int[]{16, 16, 16} ;
// Returns count of minimum operations to convert a
// zero array to arr array with increment and
// doubling operations.
// This function computes count by doing reverse
// steps, i.e., convert arr to zero array.
static int countMinOperations(int n)
{
// Initialize result (Count of minimum moves)
int result = 0;
// Keep looping while all elements of arr
// don't become 0.
while (true)
{
// To store count of zeroes in current
// arr array
int zero_count = 0;
int i; // To find first odd element
for (i=0; i<n; i++)
{
// If odd number found
if (arr[i] % 2 == 1)
break;
// If 0, then increment zero_count
else if (arr[i] == 0)
zero_count++;
}
// All numbers are 0
if (zero_count == n)
return result;
// All numbers are even
if (i == n)
{
// Divide the whole array by 2
// and increment result
for (int j=0; j<n; j++)
arr[j] = arr[j]/2;
result++;
}
// Make all odd numbers even by subtracting
// one and increment result.
for (int j=i; j<n; j++)
{
if (arr[j] %2 == 1)
{
arr[j]--;
result++;
}
}
}
}
// Driver method to test the above function
public static void main(String[] args) {
System.out.println("Minimum number of steps required to \n" +
"get the given target array is "+
countMinOperations(arr.length));
}
}
Python3
# Python3 program to count minimum number of
# operations to get the given target array
# Returns count of minimum operations to
# convert a zero array to target array
# with increment and doubling operations.
# This function computes count by doing reverse
# steps, i.e., convert target to zero array.
def countMinOperations(target, n):
# Initialize result (Count of minimum moves)
result = 0;
# Keep looping while all elements of
# target don't become 0.
while (True):
# To store count of zeroes in
# current target array
zero_count = 0;
# To find first odd element
i = 0;
while (i < n):
# If odd number found
if ((target[i] & 1) > 0):
break;
# If 0, then increment
# zero_count
elif (target[i] == 0):
zero_count += 1;
i += 1;
# All numbers are 0
if (zero_count == n):
return result;
# All numbers are even
if (i == n):
# Divide the whole array by 2
# and increment result
for j in range(n):
target[j] = target[j] // 2;
result += 1;
# Make all odd numbers even by
# subtracting one and increment result.
for j in range(i, n):
if (target[j] & 1):
target[j] -= 1;
result += 1;
# Driver Code
arr = [16, 16, 16];
n = len(arr);
print("Minimum number of steps required to",
"\nget the given target array is",
countMinOperations(arr, n));
# This code is contributed by mits
C#
// C# program to count minimum
// number of operations to get
// the given arr array */
using System;
class GFG {
static int []arr = new int[]{16, 16, 16} ;
// Returns count of minimum
// operations to convert a
// zero array to arr array
// with increment and
// doubling operations.
// This function computes
// count by doing reverse
// steps, i.e., convert arr
// to zero array.
static int countMinOperations(int n)
{
// Initialize result
// (Count of minimum moves)
int result = 0;
// Keep looping while all
// elements of arr
// don't become 0.
while (true)
{
// To store count of zeroes
// in current arr array
int zero_count = 0;
// To find first odd element
int i;
for (i = 0; i < n; i++)
{
// If odd number found
if (arr[i] % 2 == 1)
break;
// If 0, then increment
// zero_count
else if (arr[i] == 0)
zero_count++;
}
// All numbers are 0
if (zero_count == n)
return result;
// All numbers are even
if (i == n)
{
// Divide the whole array by 2
// and increment result
for(int j = 0; j < n; j++)
arr[j] = arr[j] / 2;
result++;
}
// Make all odd numbers
// even by subtracting
// one and increment result.
for(int j = i; j < n; j++)
{
if (arr[j] %2 == 1)
{
arr[j]--;
result++;
}
}
}
}
// Driver Code
public static void Main()
{
Console.Write("Minimum number of steps required to \n" +
"get the given target array is "+
countMinOperations(arr.Length));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to count minimum
// number of operations to get
// the given target array
// Returns count of minimum
// operations to convert a
// zero array to target array
// with increment and doubling
// operations.
// This function computes
// count by doing reverse
// steps, i.e., convert target
// to zero array.
function countMinOperations($target, $n)
{
// Initialize result
// (Count of minimum moves)
$result = 0;
// Keep looping while
// all elements of target
// don't become 0.
while (1)
{
// To store count of
// zeroes in current
// target array
$zero_count = 0;
// To find first
// odd element
$i = 0;
for($i = 0; $i < $n; $i++)
{
// If odd number found
if ($target[$i] & 1)
break;
// If 0, then increment
// zero_count
else if ($target[$i] == 0)
$zero_count++;
}
// All numbers are 0
if ($zero_count == $n)
return $result;
// All numbers are even
if ($i == $n)
{
// Divide the whole array by 2
// and increment result
for ($j = 0; $j < $n; $j++)
$target[$j] = $target[$j] / 2;
$result++;
}
// Make all odd numbers
// even by subtracting
// one and increment result.
for ($j = $i; $j < $n; $j++)
{
if ($target[$j] & 1)
{
$target[$j]--;
$result++;
}
}
}
}
// Driver Code
$arr= array(16, 16, 16);
$n = sizeof($arr);
echo "Minimum number of steps required to \n".
"get the given target array is ".
countMinOperations($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript program to count minimum number of operations
// to get the given arr array
let arr = [16, 16, 16] ;
// Returns count of minimum operations to convert a
// zero array to arr array with increment and
// doubling operations.
// This function computes count by doing reverse
// steps, i.e., convert arr to zero array.
function countMinOperations(n)
{
// Initialize result (Count of minimum moves)
let result = 0;
// Keep looping while all elements of arr
// don't become 0.
while (true)
{
// To store count of zeroes in current
// arr array
let zero_count = 0;
let i; // To find first odd element
for (i=0; i<n; i++)
{
// If odd number found
if (arr[i] % 2 == 1)
break;
// If 0, then increment zero_count
else if (arr[i] == 0)
zero_count++;
}
// All numbers are 0
if (zero_count == n)
return result;
// All numbers are even
if (i == n)
{
// Divide the whole array by 2
// and increment result
for (let j=0; j<n; j++)
arr[j] = arr[j]/2;
result++;
}
// Make all odd numbers even by subtracting
// one and increment result.
for (let j=i; j<n; j++)
{
if (arr[j] %2 == 1)
{
arr[j]--;
result++;
}
}
}
}
// Driver Code
document.write("Minimum number of steps required to " + "<br/>" +
"get the given target array is "+
countMinOperations(arr.length));
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA