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


Сложный уровень Жесткий
Часто спрашивают в Cadence Индия Де Шоу 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

объяснение

Type3 (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.

Type3 (2, 4) после произведения всех элементов в диапазоне 3 и 5 ⇒ 2 * 3 * 40 = 240

Выходные данные ⇒ 3. Таким образом, в запросах типа 3 мы нашли всего 3 конечных нуля, поэтому он печатается.

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

 

Алгоритм

  1. Объявите два массива, чтобы в обоих массивах сохранялось количество конечных нулей относительно чисел 2 и 5 соответственно.
  2. Если мы вызываем type1, то получаем конечные нули X в терминах 2 и 5.
  3. Пройдите по массиву в заданном диапазоне. Умножьте каждое число на значение X. Одновременно сохраните значение нулей как кратное 2 и 5 в массив, который мы создали для zeroesInTwo и нулиInFive.
  4. Если мы вызываем type2, снова получаем конечные нули Y в терминах 2 и 5.
  5. Сохраните Y в первой позиции диапазона, 2Y во второй и так далее. Одновременно сохраните количество конечных нулей до zeroesInTwo и zeroesInFive.
  6. А для type3 получите сумму всех значений, которые находятся в диапазоне от 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) времени, потому что мы должны пройти весь предоставленный нам диапазон.

Космическая сложность

О (п) в котором «Н» - количество элементов в массиве. Поскольку мы создали два массива, кроме входных, алгоритм имеет линейную пространственную сложность.