Rayանգվածի հարցումներ բազմապատկվող փոխարինումների և արտադրանքի համար  


Դժվարության մակարդակ Դժվար
Հաճախակի հարցնում են Կադենս Հնդկաստան ԴԵ Շոուն Expedia Google
Դասավորություն Հարցման խնդիր

«Բազմապատկման, փոխարինման և արտադրանքի հարցումների զանգվածի» խնդրում նշված է, որ ձեզ տրված է դասավորություն of ամբողջ թիվ և կլինեն երեք տեսակի հարցումներ, որտեղ դուք պետք է լուծեք հետևյալ տեսակի հարցումները.

Տեսակ 1. Ձախ, աջ և X թվեր կլինեն երեք: Այս տեսակի հարցումներում պետք է զանգվածի յուրաքանչյուր տարր բազմապատկել տիրույթի X արժեքի (ձախ, աջ) ներառյալ:

Տեսակ 2. Այն բաղկացած է երեք արժեքներից ՝ ձախ, աջ ՝ որպես տիրույթ: Տրված տիրույթի տարրերը պետք է փոխարինեք Y, 2Y, 3Y և այլն թվերով:

Տեսակ 3. Որպես միջակայք ՝ կլինի ձախ և աջ երկու արժեք: Տրված տիրույթում պետք է գտնեք բոլոր տարրերի արտադրանքը: Քանի որ թիվը կարող է մեծ լինել: Պետք է հաշվել հետևող զրոների ընդհանուր քանակը Type3 բոլոր հարցումներում:

Օրինակ  

arr[] = {1, 2, 3, 4, 5}
Query: { (3,2,5), (3,4,5), (2,1,3,1), (1,4,5,10), (3,2,4)}
3

բացատրություն

Type 3 (2, 5), 2 և 5 the 2 3 4 * 5 * 120 * XNUMX = XNUMX միջակայքում գտնվող բոլոր տարրերի արտադրանքից հետո

Type 3 (3, 5), 3 և 5 the 3 * 4 * 5 = 60 միջակայքում գտնվող բոլոր տարրերի արտադրանքից հետո

Type2 (1, 3, 1), յուրաքանչյուր տարրը y, 2y և 3y- ով փոխարինելուց հետո և այլն 1-ից 3-ի սահմաններում

Type1 (4, 5, 10), յուրաքանչյուր տարրը բազմապատկիր 10-ով 4-ից 5-ի սահմաններում

Տես նաեւ,
Ապրանքի առավելագույն ենթաշղթա

Type 3 (2, 4), 3 և 5 range 2 * 3 * 40 = 240 միջակայքում գտնվող բոլոր տարրերի արտադրանքից հետո

Արդյունք ⇒ 3, այնպես որ, ընդհանուր առմամբ, կլինեն 3 հետևող զրոներ, որոնք մենք գտել ենք 3-րդ տիպի հարցումներում, ուստի այն տպվում է:

Rayանգվածի հարցումներ բազմապատկման, փոխարինումների և արտադրանքի համարPin

 

Ալգորիթմ  

  1. Հայտարարեք երկու զանգված այնպիսին, որ երկու զանգվածներն էլ կպահպանեն հետևող զրոների քանակը համապատասխանաբար 2 և 5 թվերի համեմատ:
  2. Եթե ​​մենք կոչ ենք անում type1- ին, ապա ստացիր X- ի հետևող զրոները ՝ 2-ի և 5-ի առումով:
  3. Տրված տիրույթում զանգվածի միջով անցում: Յուրաքանչյուր համարը բազմապատկիր X արժեքով: Միաժամանակ զրոների արժեքը պահիր որպես 2-ի և 5-ի բազմապատիկ `մեր համար ստեղծված զանգվածում: զրոներ Երկու և zeroesInFive.
  4. Եթե ​​մենք կոչ ենք անում type2- ին, ապա կրկին ստացեք Y- ի հետևող զրոները `2-ի և 5-ի առումով:
  5. Պահպանեք Y- ն տիրույթի առաջին դիրքում, 2Y երկրորդը և այլն: Միաժամանակ պահեք հետևող զրոների քանակը դեպի զրոներInTwo և zeroesInFive:
  6. Իսկ տիպ 3-ի համար ստացիր բոլոր արժեքների հանրագումարը, որոնք գտնվում են զրոների InTwo- ում և ZeroesInFive- ում, և պարզիր զրոների քանակի նվազագույնը երկուում կամ զրոների քանակում հինգում:
  7. Արժեքը տպիր գումարով:

բացատրություն  

Մեզ տրված է ամբողջ զանգված և լուծելու երեք տեսակի հարցումներ: Հարցումներից մեկն ասում է, որ միջակայքում պետք է ինչ-որ թիվ բազմապատկել: Մյուսն ասում է, որ որոշ թվեր պետք է փոխարինես: Վերջինը ասում է, որ դուք պետք է թվերի արտադրյալը գտնեք տիրույթում: Այնուհետև հարցումներից յուրաքանչյուրը կատարելու համար մենք առանձնացրել ենք երեք գործառույթները, որոնք համապատասխանաբար կատարում են իրենց մասը յուրաքանչյուր հարցման համար: Դրանից հետո մենք կիմանանք հետի զրոները: Դրա համար մենք երկու զանգված ենք ստեղծել, մեկը `2-ի համար, իսկ մյուսը` 5-ի:

Տես նաեւ,
Երկուական որոնման եզակի ծառեր

Առաջին տեսակի հարցումը լուծելու համար մեզ կտրվի X թիվ և տիրույթ `ելակետի և ավարտի կետի առումով: Պարզելու համար, թե որոնք են հետևի զրոները: Մենք կպարզենք, արդյոք տրված համարն ունի այդ հետին զրոները: Դրանից հետո ստացեք այս հետին զրոների հաշվարկը: Նույնը հինգի առումով զրոների հետ վարվելն է: Մենք կշրջանցենք զանգվածը ՝ տիրույթի մեկնարկային կետից մինչև միջակայքի վերջնակետ: Դրանից հետո մենք անցնելիս բազմապատկելու ենք X արժեքը յուրաքանչյուր համարի հետ: Մենք նաև միաժամանակ կատարելու ենք լրացումներ այն զանգվածի վրա, որը ստեղծում ենք զրոներ պահելու համար: Նույնը `2-րդ տիպի հարցում կատարելն է, պարզապես անհրաժեշտ է յուրաքանչյուր տարր փոխարինել տրված թվով` շարքերի տեսքով:

Երրորդ տիպի հարցումը լուծելու համար մենք սահմանելու ենք sumOfTwos և sumOfFives մինչև 0. Մենք արժեքը կպահպանենք մեր ստեղծած sumOfTwos- ի և sumOfFives- ի փոփոխականում: Դրանից հետո մենք կիմանանք sumOfTwos- ի և sumOfFives- ի նվազագույնը: Դա կլինի պահանջվող և վերջնական պատասխանը, որը մենք կվերադառնանք:

Կոդ  

Իրականացում C ++ - ում `զանգվածի հարցումների բազմապատկման, փոխարինումների և արտադրանքի համար

#include<vector>
#include<iostream>

using namespace std;

vector<int> zeroesInTwo(1000,0);

vector<int> zeroesInFive(1000,0);

int sum = 0;

int getTwosZeroes(int val)
{
    int count = 0;
    while (val % 2 == 0 && val != 0)
    {

        val = val / 2;
        count++;
    }

    return count;
}

int getFivesZeroes(int val)
{
    int count = 0;
    while (val % 5 == 0 && val != 0)
    {

        val = val / 5;
        count++;
    }

    return count;
}

void type1(int arr[],int ql, int qr, int x)
{
    int twoCount = getTwosZeroes(x);
    int fiveCount = getFivesZeroes(x);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = arr[i] * x;

        zeroesInTwo[i] += twoCount;
        zeroesInFive[i] += fiveCount;
    }
}

void type2(int arr[], int ql, int qr, int y)
{
    int twoCount = getTwosZeroes(y);
    int fiveCount = getFivesZeroes(y);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = (i - ql + 2) * y;

        zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
        zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
    }
}

void type3(int arr[],int ql, int qr)
{
    int sumtwos = 0;
    int sumfives = 0;

    for (int i = ql - 1; i < qr; i++)
    {
        sumtwos += zeroesInTwo[i];
        sumfives += zeroesInFive[i];
    }
    sum += min(sumtwos, sumfives);

}

int main()
{
    int arr[]= {1,2,3,4,5};

    int n=sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < n; i++)
    {
        zeroesInTwo[i] = getTwosZeroes(arr[i]);
        zeroesInFive[i] = getFivesZeroes(arr[i]);
    }
    type3(arr,2,5);
    type3(arr,4,5);

    type2(arr,1,3,1);
    type1(arr,4,5,10);

    type3(arr,2,4);

    cout << sum << endl;
    return 0;
}
3

Իրականացում Java- ում Array հարցումների համար բազմապատկման, փոխարինումների և արտադրանքի համար

import java.util.*;

class type123
{
    private static int zeroesInTwo[]=new int[1000];

    private static int zeroesInFive[]=new int[1000];



    private static int sum = 0;

    private static int getTwosZeroes(int val)
    {
        int count = 0;
        while (val % 2 == 0 && val != 0)
        {

            val = val / 2;
            count++;
        }

        return count;
    }

    private static int getFivesZeroes(int val)
    {
        int count = 0;
        while (val % 5 == 0 && val != 0)
        {

            val = val / 5;
            count++;
        }

        return count;
    }

    private static void type1(int arr[],int ql, int qr, int x)
    {
        int twoCount = getTwosZeroes(x);
        int fiveCount = getFivesZeroes(x);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = arr[i] * x;

            zeroesInTwo[i] += twoCount;
            zeroesInFive[i] += fiveCount;
        }
    }

    private static void type2(int arr[], int ql, int qr, int y)
    {
        int twoCount = getTwosZeroes(y);
        int fiveCount = getFivesZeroes(y);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = (i - ql + 2) * y;

            zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
            zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
        }
    }

    private static void type3(int arr[],int ql, int qr)
    {
        int sumtwos = 0;
        int sumfives = 0;

        for (int i = ql - 1; i < qr; i++)
        {
            sumtwos += zeroesInTwo[i];
            sumfives += zeroesInFive[i];
        }
        sum += Math.min(sumtwos, sumfives);

    }

    public static void main(String []args)
    {
        int arr[]= {1,2,3,4,5};

        int n=arr.length;

        Arrays.fill(zeroesInTwo,0);

        Arrays.fill(zeroesInFive,0);

        for (int i = 0; i < n; i++)
        {
            zeroesInTwo[i] = getTwosZeroes(arr[i]);
            zeroesInFive[i] = getFivesZeroes(arr[i]);
        }

        type3(arr,2,5);
        type3(arr,4,5);

        type2(arr,1,3,1);
        type1(arr,4,5,10);

        type3(arr,2,4);

        System.out.println(sum);

    }
}
3

Բարդության վերլուծություն  

Timeամանակի բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Յուրաքանչյուր հարցման համար պահանջվում է O (N) ժամանակ, քանի որ մենք պետք է անցնենք մեզ տրված տիրույթի ամբողջ մասը:

Տես նաեւ,
Սկզբից բացակայում է դրականը

Տիեզերական բարդություն

O (n) որտեղ «Ն» զանգվածում տարրերի քանակն է: Քանի որ մենք մուտքագրումից բացի ստեղծել ենք այլ երկու զանգված, ալգորիթմը գծային տիեզերական բարդություն ունի: