Запыты масіва для множнай замены і прадукту


Узровень складанасці Жорсткі
Часта пытаюцца ў Cadence Індыя DE Шоу 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

Тлумачэнне

Тып3 (2, 5), пасля здабытку ўсіх элементаў у дыяпазоне 2 і 5 ⇒ 2 * 3 * 4 * 5 = 120

Тып 3 (3, 5), пасля атрымання ўсіх элементаў у дыяпазоне 3 і 5 ⇒ 3 * 4 * 5 = 60

Type2 (1, 3, 1), пасля замены кожнага элемента на y, 2y і 3y і гэтак далей у дыяпазоне ад 1 да 3

Тып 1 (4, 5, 10), памножце кожны элемент на 10 у дыяпазоне ад 4 да 5

Тып3 (2, 4) пасля здабытку ўсіх элементаў у дыяпазоне 3 і 5 ⇒ 2 * 3 * 40 = 240

Выхад ⇒ 3, значыць, у агульнай складанасці будзе 3 нуля, якія мы знайшлі ў запытах тыпу 3, таму ён будзе надрукаваны.

Запыты масіва для множання, замены і прадукту

 

Алгарытм

  1. Абвясціце два масівы такім чынам, каб абодва масіва захоўвалі колькасць завяршальных нулёў адносна лікаў 2 і 5 адпаведна.
  2. Калі мы заклікаем да type1, то атрымаем нулі X, з пункту гледжання 2 і 5.
  3. Прайсці праз масіў у зададзеным дыяпазоне. Памножце кожны лік на значэнне X. Адначасова захавайце значэнне нулёў, кратнае 2 і 5, у масіў, для якога мы стварылі нуліInTwo і нулі InFive.
  4. Калі мы патрабуем type2, зноў атрымаем нулі Y, з пункту гледжання 2 і 5.
  5. Захоўвайце Y у першай пазіцыі дыяпазону, 2Y на другой і гэтак далей. Адначасова захоўвайце падлік нулявых нулёў да zeroesInTwo і zeroesInFive.
  6. А для тыпу3 атрымайце суму ўсіх значэнняў, якія знаходзяцца ў дыяпазоне ў zeroesInTwo і 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 для запытаў масіваў для множання, замены і прадукту

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

Аналіз складанасці

Складанасць часу

Аб (п) дзе "П" - колькасць элементаў у масіве. Для кожнага запыту патрабуецца час O (N), таму што мы павінны прайсці ўвесь дыяпазон, дадзены нам.

Касмічная складанасць

Аб (п) дзе "П" - колькасць элементаў у масіве. Паколькі мы стварылі два масівы, акрамя ўваходных, алгарытм мае лінейную складанасць прасторы.