Cuente los pasos mínimos para obtener la array deseada dada

Considere una array con n elementos y el valor de todos los elementos es cero. Podemos realizar las siguientes operaciones en la array. 

  1. Operaciones incrementales: elija 1 elemento de la array e incremente su valor en 1.
  2. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *