Verilən istənilən serialı əldə etmək üçün minimum addımları sayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Capital One Citrix Coursera Sinopsis Zikus
Geyim RiyaziyyatBaxılıb 25

Problem bəyanat

Tutaq ki, bütün elementləri kimi yalnız 0 ədədi olan bir sıra var. Nəzərə alın, sizə bir sıra uzunluq verilir n 0'ları verilən lazımi sıraya çevirməli olduğumuz bütün 0-lara sahibik. Lazımi massivi Arzu massiv. Beləliklə, verilən istənilən serialı əldə etmək üçün minimum addımları saymalıyıq. Yəni sıfır cərgəni verilmiş tələb olunan cərgəyə dəyişdirməli olan mümkün əməliyyatların minimum sayını tapmaqdır. Yalnız aşağıdakı əməliyyatları edə bilərik.

  1. Əməliyyatın ikiqat artırılması: Ya bir sıra elementinin dəyərini iki dəfə artıra bilərik, ya da
  2. Artımlı əməliyyatlar: Dizinin dəyərinin elementini 1 artıra bilərik.

 

misal

desiredArr[] = {1, 2}
3

Explanation:

{0,0} istənənə çevirin array

  • Elementin hər iki dəyərini 1 → (2 əməliyyat) artırın
  • İkinci elementi 1 → artırın (1 əməliyyat daha)
  • Bu, cəmi 3 əməliyyatdır.

 

desiredArr[] = {4, 2}
4

Explanation:

  • Elementin hər iki dəyərini 1 → (2 əməliyyat) artırın
  • Bütün sıra elementlərinin dəyərini iki dəfə artırın → (1 əməliyyat)
  • Birinci elementi iki dəfə artırın → (1 əməliyyat daha)
  • Bu, cəmi 4 əməliyyatdır.

 

Verilən istənilən massivi əldə etmək üçün minimum addımları saymaq üçün alqoritm

1. Get the desiredArr array.
2. Set output as 0.
3. Check if all the elements given are even, then divide all the elements by 2 and increase the output by 1.
4. Get all of the odd elements, make them even by decrease their value by 1.
5. For every decrement, increase the value of output by 1.
6. We get all zeros in desiredArr array, after completing all the steps.
7. Return output.

 

Izahat

Giriş massivini verdik və fərz edək ki, yalnız 0 elementini özündə cəmləşdirdiyimiz, verilmiş istənilən massivi əldə etmək üçün minimum addımları saymaq üçün bir əməliyyat yerinə yetirmək istədiyimiz bir sıra var. Həyata keçirilən əməliyyatlar verilmiş təlimatları təmin etməlidir. Demək lazım olan massivi yalnız verilmiş təlimatları təmin edən əməliyyatlar yerinə yetiririk.

Birinci əməliyyat, serialın element dəyərini 1-ə qədər artıra bilərik. Bu, n əməliyyatda sayılır, o deməkdir ki, elementin dəyərinin sayını 1-ə artırırıqsa, ikinci əməliyyat bütün elementi deyil, elementi iki qat artırmaqdır. bütün massivi 2-yə vurun. Beləliklə, bütün massivi 2-yə vursaq, 1 əməliyyatı yerinə yetirə bilərik. Beləliklə, hər iki dəyərin 1-i artırılaraq əməliyyat sayını hesablasaq və sonra massivi bir dəfə iki dəfə artırsaq, bu, ümumi əməliyyat sayının 3-ə bərabər olduğunu göstərir.

Nümunəni arr [] = {4, 2} olaraq götürə bilərik və 0s-lıq bir sıra olduğumuzu düşünməliyik. Buna görə əvvəlcə elementlərin dəyərini 1 artırmalıyıq, buna görə 2 əməliyyatı sayırıq. İndi bir sıra olaraq {1, 1} var. İndi bütün serialı iki dəfə artırırıq, beləliklə {2, 2} və 3 əməliyyat əldə edirik. İlk vəziyyətdə 4-ə sahib olmalıyıq. Buna görə bu dəyəri iki dəfə artırırıq və bu günə qədər ümumilikdə 4 əməliyyat etdik. 4 istədiyiniz sıra almaq üçün minimum addım sayımızdır.

Bu, sadəcə intuitiv bir anlayış yolu idi. Ancaq bunu etmək əvəzinə giriş serialını 0-lar sırasına çevirəcəyik. Beləliklə, bunu etmək üçün verilmiş əməliyyatların əksinə çıxış edirik. Elementlər tək olduqda azaldırıq və bir dəfə massivin bütün elementlərinə sahib olduq. Onların hər birini (massivdəki elementləri) 2-yə böldük və bu tək bir əməliyyat sayılır. Məsələn [4,2] -> [2,1] -> [2,0] -> [1,0] -> [0,0] kimi göstərildiyi kimi dəyişsə də.

Qeyd

Bu texnika digər problemlərdə də istifadə olunur. Bənzər təlimatlardan istifadə edərək tam A-nın B-yə çevrilməsi bunlardan biridir. A-nı 1-ə endirə və ya A-nı 2-yə çoxaldıra bilərik, bir daha B-ni A-ya çevirməyə çalışırıq, bu təklif olunan problemin digər həllinə nisbətən daha asandır.

 

Verilən istənilən serialı əldə etmək üçün minimum addımları sayınPin

Verilən istənilən sıra almaq üçün minimum addımları saymaq üçün kod

C ++ kodu

#include<iostream>
using namespace std;

int getMinimumOperations(unsigned int desiredArr[], int n)
{
    int output = 0;
    while (1)
    {
        int zeroArrCnt= 0;

        int i;
        for (i=0; i<n; i++)
        {
            if (desiredArr[i] & 1)
                break;

            else if (desiredArr[i] == 0)
                zeroArrCnt++;
        }
        if (zeroArrCnt== n)
            return output;
        if (i == n)
        {
            for (int j=0; j<n; j++)
                desiredArr[j] = desiredArr[j]/2;
            output++;
        }
        for (int j=i; j<n; j++)
        {
            if (desiredArr[j] & 1)
            {
                desiredArr[j]--;
                output++;
            }
        }
    }
}
int main()
{
    unsigned int arr[] = {4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout <<getMinimumOperations(arr, n);
    return 0;
}
4

Java kodu

class minimumSteps
{
    public static int getMinimumOperations(int arr[],int n)
    {
        int output = 0;
        while (true)
        {

            int zeroArrCnt= 0;

            int i;
            for (i=0; i<n; i++)
            {
                if (arr[i] % 2 == 1)
                    break;
                else if (arr[i] == 0)
                    zeroArrCnt++;
            }
            if (zeroArrCnt== n)
                return output;

            if (i == n)
            {
                for (int j=0; j<n; j++)
                    arr[j] = arr[j]/2;
                output++;
            }
            for (int j=i; j<n; j++)
            {
                if (arr[j] %2 == 1)
                {
                    arr[j]--;
                    output++;
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int arr[] = {4, 2} ;
        System.out.println(getMinimumOperations(arr,arr.length));
    }
}
4

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n) hara "N" massivdəki elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" massivdəki elementlərin sayıdır.

Translate »