Берілген қажетті массивті алу үшін минималды қадамдарды санаңыз


Күрделілік дәрежесі орта
Жиі кіреді Capital One Citrix Coursera Synopsys Zycus
Array математика

Проблемалық мәлімдеме

Сізде оның барлық элементтері ретінде тек 0 бүтін саны бар жиым бар делік. Сізге ұзындық массиві берілгенін қарастырайық n біз 0-ді берілген жиымға айналдыруымыз керек барлық 0-ге ие боламыз. Қажетті массивті Arr массив. Осылайша, қажетті массивті алу үшін минималды қадамдарды санауымыз керек. Мүмкін болатын амалдардың минималды санын анықтау үшін нөлдік жиымды берілген қажетті массивке өзгерту керек. Біз тек келесі операцияларды жасай аламыз.

  1. Екі еселенген жұмыс: немесе біз массивтің элементтік мәнін екі есеге арттыра аламыз, немесе
  2. Қосымша амалдар: массивтің мәнін 1-ге көбейтуге болады.

 

мысал

desiredArr[] = {1, 2}
3

Түсіндіру:

{0,0} қалағанына ауыстыру массив

  • Элементтің екі мәнін де 1 → (2 амал) арттырыңыз
  • Екінші элементті 1 → көбейтіңіз (тағы 1 әрекет)
  • Бұл барлығы 3 операцияны құрайды.

 

desiredArr[] = {4, 2}
4

Түсіндіру:

  • Элементтің екі мәнін де 1 → (2 амал) арттырыңыз
  • Массив элементтерінің барлық мәнін екі есеге көбейту → (1 амал)
  • Бірінші элементті екі есеге көбейту → (тағы 1 әрекет)
  • Бұл барлығы 4 операцияны құрайды.

 

Берілген қажетті жиымды алу үшін минималды қадамдарды санау алгоритмі

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.

 

Түсіндіру

Біз енгізу жиымын бердік, сонымен қатар бізде тек 0 элементі бар жиым бар деп ойлаймыз, оған берілген жиымға жету үшін минималды қадамдарды санау операциясын жасағымыз келеді. Орындалған операциялар берілген нұсқауларды қанағаттандыруы керек. Бұл дегеніміз, біз қажетті массивті тек берілген нұсқауларды қанағаттандыратын әрекеттерді орындай отырып жасаймыз.

Бірінші амал - біз массивтің элемент мәнін 1-ге көбейте аламыз, бұл n амалға есептеледі, демек, егер элементтің мәнінің санын 1-ге көбейтсек, екінші амал - бұл массивті екі есе көбейту емес, элементті көбейту. барлық массивті 2-ге көбейтіңіз. Егер біз жиымның барлығын 2-ге көбейтсек, онда 1 амал орындалады. Сонымен, егер біз мәндердің екеуін де 1-ге көбейтіп, амалдар санын санап, массивті бір рет екі есеге көбейтсек, бұл амалдардың жалпы саны 3-ке тең болатындығын білдіреді.

Біз мысалды arr [] = {4, 2} түрінде ала аламыз, сонымен қатар бізде 0s жиымы бар деп ойлауымыз керек. Сонымен, алдымен элементтердің мәнін 1-ге арттыру керек, сондықтан 2 амал санап шығамыз. Енді бізде массив ретінде {1, 1} бар. Енді біз бүкіл массивті екі есеге көбейтеміз, сонда {2, 2} және 3 амал аламыз. Бізде бірінші позицияда 4 болуы керек. Ол үшін біз бұл мәнді екі есеге арттырамыз және осы уақытқа дейін барлығы 4 операция жасадық. 4 - бұл қажетті массивті алу үшін минималды қадамдар саны.

Бұл жай ғана түсінудің интуитивті тәсілі болды. Бірақ мұны жасаудың орнына біз енгізу массивін 0 санына айналдырамыз. Сонымен, бұл үшін біз берілген амалдарға қарама-қарсы әрекет жасаймыз. Егер элементтер тақ болса, оларды кемітеміз, ал егер массивтің барлық элементтері болса. Біз олардың әрқайсысын (массивтегі элементтерді) 2-ге бөлеміз және бұл бір амал ретінде есептеледі. Мысалы [4,2] -> [2,1] -> [2,0] -> [1,0] -> [0,0] сияқты, көрсетілгендей өзгереді.

Ескерту

Бұл әдіс басқа мәселелерде де қолданылады. Ұқсас нұсқауларды қолдана отырып, бүтін А-ны В-ға айналдыру олардың бірі болып табылады. Біз А-ны 1-ге азайта аламыз немесе А-ны 2-ге көбейте аламыз, тағы бір рет В-ны А-ға ауыстыруға тырысамыз, бұл ұсынылған есептің басқа шешімімен салыстырғанда әлдеқайда жеңіл.

 

Берілген қажетті массивті алу үшін минималды қадамдарды санаңыз

Берілген қажетті массивті алу үшін минималды қадамдарды есептейтін код

C ++ коды

#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 коды

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.

Ғарыштың күрделілігі

O (N) қайда «N» - бұл массивтегі элементтер саны.