Рубрики

Посчитайте минимальные шаги, чтобы получить заданный желаемый массив

Рассмотрим массив с n элементами, а значение всех элементов равно нулю. Мы можем выполнить следующие операции над массивом.

  1. Инкрементные операции: выберите 1 элемент из массива и увеличьте его значение на 1.
  2. Операция удвоения: Удвойте значения всех элементов массива.

Нам дан желаемый массив target [], содержащий n элементов. Вычислить и вернуть наименьшее возможное количество операций, необходимых для изменения массива со всех нулей на требуемый массив.

Примеры:

Input: target[] = {2, 3}
Output: 4
To get the target array from {0, 0}, we 
first increment both elements by 1 (2 
operations), then double the array (1 
operation). Finally increment second
element (1 more operation)

Input: target[] = {2, 1}
Output: 3
One of the optimal solution is to apply the 
incremental operation 2 times to first and 
once on second element.

Input: target[] = {16, 16, 16}
Output: 7
The output solution looks as follows. First 
apply an incremental operation to each element. 
Then apply the doubling operation four times. 
Total number of operations is 3+4 = 7

Важно отметить, что задача состоит в том, чтобы подсчитать количество шагов для получения заданного целевого массива (а не для преобразования нулевого массива в целевой массив).

Идея состоит в том, чтобы следовать обратным шагам, то есть преобразовать цель в массив нулей. Ниже приведены шаги.

Take the target array first. 

Initialize result as 0. 

If all are even, divide all elements by 2 
and increment result by 1. 

Find all odd elements, make them even by 
reducing them by 1. and for every reduction,
increment result by 1.

Finally, we get all zeros in target array.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

/ * C ++ программа для подсчета минимального количества операций

   получить заданный целевой массив * /

#include <bits/stdc++.h>

using namespace std;

  
// Возвращает количество минимальных операций для преобразования
// нулевой массив для целевого массива с приращением и
// операции удвоения.
// Эта функция вычисляет счет, делая обратный
// шаги, т.е. преобразовать цель в нулевой массив.

int countMinOperations(unsigned int target[], int n)

{

    // Инициализировать результат (количество минимальных ходов)

    int result = 0;

  

    // Продолжаем цикл пока все элементы цели

    // не становиться 0.

    while (1)

    {

        // Хранить количество нулей в текущем

        // целевой массив

        int zero_count = 0;

  

        int i;  // Чтобы найти первый нечетный элемент

        for (i=0; i<n; i++)

        {

            // Если найдено нечетное число

            if (target[i] & 1)

                break;

  

            // Если 0, то увеличивать zero_count

            else if (target[i] == 0)

                zero_count++;

        }

  

        // Все числа равны 0

        if (zero_count == n)

          return result;

  

        // Все числа четные

        if (i == n)

        {

            // Делим весь массив на 2

            // и увеличиваем результат

            for (int j=0; j<n; j++)

               target[j] = target[j]/2;

            result++;

        }

  

        // сделать все нечетные числа четными, вычитая

        // единичный и инкрементальный результат.

        for (int j=i; j<n; j++)

        {

           if (target[j] & 1)

           {

              target[j]--;

              result++;

           }

        }

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

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-программа для подсчета минимального количества операций

   получить заданный массив arr * /

   

class Test

{

    static int arr[] = new int[]{16, 16, 16} ;

       

    // Возвращает количество минимальных операций для преобразования

    // нулевой массив к массиву arr с инкрементом и

    // операции удвоения.

    // Эта функция вычисляет счет, делая обратный

    // шаги, т.е. преобразовать arr в нулевой массив.

    static int countMinOperations(int n)

    {

        // Инициализировать результат (количество минимальных ходов)

        int result = 0;

       

        // Продолжаем цикл пока все элементы обр

        // не становиться 0.

        while (true)

        {

            // Хранить количество нулей в текущем

            // массив arr

            int zero_count = 0;

       

            int i;  // Чтобы найти первый нечетный элемент

            for (i=0; i<n; i++)

            {

                // Если найдено нечетное число

                if (arr[i] % 2 == 1)

                    break;

       

                // Если 0, то увеличивать zero_count

                else if (arr[i] == 0)

                    zero_count++;

            }

       

            // Все числа равны 0

            if (zero_count == n)

              return result;

       

            // Все числа четные

            if (i == n)

            {

                // Делим весь массив на 2

                // и увеличиваем результат

                for (int j=0; j<n; j++)

                   arr[j] = arr[j]/2;

                result++;

            }

       

            // сделать все нечетные числа четными, вычитая

            // единичный и инкрементальный результат.

            for (int j=i; j<n; j++)

            {

               if (arr[j] %2 == 1)

               {

                  arr[j]--;

                  result++;

               }

            }

        }

    }

    

    // Метод драйвера для проверки вышеуказанной функции

    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 программа для подсчета минимального количества
# операций для получения заданного целевого массива

  
# Возвращает количество минимальных операций
# преобразовать нулевой массив в целевой массив
# с операциями приращения и удвоения.
# Эта функция вычисляет количество, делая обратный
# шагов, т.е. конвертировать цель в нулевой массив.

def countMinOperations(target, n): 

      

    # Инициализировать результат (Количество минимальных ходов)

    result = 0

  

    # Продолжайте цикл пока все элементы

    # цель не становится 0.

    while (True): 

          

        # Хранить количество нулей в

        # текущий целевой массив

        zero_count = 0

      

        # Чтобы найти первый нечетный элемент

        i = 0

        while (i < n):

              

            # Если найдено нечетное число

            if ((target[i] & 1) > 0): 

                break

  

            # Если 0, то приращение

            # zero_count

            elif (target[i] == 0): 

                zero_count += 1;

            i += 1;

  

        # Все цифры 0

        if (zero_count == n): 

            return result; 

  

        # Все числа четные

        if (i == n): 

              

            # Разделите весь массив на 2

            # и результат приращения

            for j in range(n):

                target[j] = target[j] // 2

            result += 1

  

        # Сделать все нечетные числа четными

        # вычитая единицу и увеличивая результат.

        for j in range(i, n): 

            if (target[j] & 1): 

                target[j] -= 1

                result += 1

  
Код водителя

arr = [16, 16, 16]; 

n = len(arr); 

print("Minimum number of steps required to",

          "\nget the given target array is",

                countMinOperations(arr, n)); 

  
# Этот код предоставлен mits

C #

// C # программа для подсчета минимума
// количество операций для получения
// заданный массив arr * /

using System; 

class GFG {

      

    static int []arr = new int[]{16, 16, 16} ;

      

    // Возвращает количество минимумов

    // операции для преобразования

    // массив от нуля до массива arr

    // с шагом и

    // операции удвоения.

    // Эта функция вычисляет

    // считать, делая обратный

    // шаги, т.е. конвертируем обр

    // к нулевому массиву.

    static int countMinOperations(int n)

    {

          

        // Инициализировать результат

        // (Количество минимальных ходов)

        int result = 0;

      

        // Продолжаем цикл пока все

        // элементы обр

        // не становиться 0.

        while (true)

        {

              

            // Хранить количество нулей

            // в текущем массиве arr

            int zero_count = 0;

      

            // Чтобы найти первый нечетный элемент

            int i; 

            for (i = 0; i < n; i++)

            {

                  

                // Если найдено нечетное число

                if (arr[i] % 2 == 1)

                    break;

      

                // Если 0, то приращение

                // zero_count

                else if (arr[i] == 0)

                    zero_count++;

            }

      

            // Все числа равны 0

            if (zero_count == n)

            return result;

      

            // Все числа четные

            if (i == n)

            {

                  

                // Делим весь массив на 2

                // и увеличиваем результат

                for(int j = 0; j < n; j++)

                arr[j] = arr[j] / 2;

                result++;

            }

      

            // Сделать все нечетные числа

            // даже вычитая

            // единичный и инкрементальный результат.

            for(int j = i; j < n; j++)

            {

                if (arr[j] %2 == 1)

                {

                    arr[j]--;

                    result++;

                }

            }

        }

    }

      

    // Код драйвера

    public static void Main()

    {

        Console.Write("Minimum number of steps required to \n"

                            "get the given target array is "+

                                countMinOperations(arr.Length));

      

    }

}

  
// Этот код предоставлен нитин митталь.

PHP

<?php
// PHP программа для подсчета минимума
// количество операций для получения
// заданный целевой массив

  
// Возвращает количество минимумов
// операции для преобразования
// нулевой массив к целевому массиву
// с увеличением и удвоением
// операции.
// Эта функция вычисляет
// считать, делая обратный
// шаги, т.е. конвертировать цель
// к нулевому массиву.

function countMinOperations($target, $n)

{

      

    // Инициализировать результат

    // (Количество минимальных ходов)

    $result = 0;

  

    // Продолжаем цикл пока

    // все элементы цели

    // не становиться 0.

    while (1)

    {

          

        // Для сохранения количества

        // нули в токе

        // целевой массив

        $zero_count = 0;

      

        // Найти первым

        // нечетный элемент

        $i = 0; 

        for($i = 0; $i < $n; $i++)

        {

              

            // Если найдено нечетное число

            if ($target[$i] & 1)

                break;

  

            // Если 0, то приращение

            // zero_count

            else if ($target[$i] == 0)

                $zero_count++;

        }

  

        // Все числа равны 0

        if ($zero_count == $n)

            return $result;

  

        // Все числа четные

        if ($i == $n)

        {

              

            // Делим весь массив на 2

            // и увеличиваем результат

            for ($j = 0; $j < $n; $j++)

            $target[$j] = $target[$j] / 2;

            $result++;

        }

  

        // Сделать все нечетные числа

        // даже вычитая

        // единичный и инкрементальный результат.

        for ($j = $i; $j < $n; $j++)

        {

            if ($target[$j] & 1)

            {

                $target[$j]--;

                $result++;

            }

        }

    }

}

  

    // Код драйвера

    $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);

  
// Этот код предоставлен mits
?>


Выход :

Minimum number of steps required to 
get the given target array is 7

Эта статья предоставлена Шивам Агравал . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Посчитайте минимальные шаги, чтобы получить заданный желаемый массив

0.00 (0%) 0 votes