Вивести змінений масив після виконання команд додавання та віднімання


Рівень складності Medium
Часто запитують у ByteDance Cisco Citrix FreeCharge Хакер Rank Нагарро працювати Терадата
масив

Вам надається масив розміром n, спочатку всі значення в масиві будуть дорівнювати 0, а запити. Кожен запит містить чотири значення, тип запиту T, ліву точку діапазону, праву точку діапазону та число k, вам потрібно виконати наступні операції.

Якщо T = 0, додайте значення k до всіх цілих чисел у межах заданого діапазону (початку, кінця) у даному масиві,

Якщо T = 1, відніміть значення k з усіх цілих чисел у межах заданого діапазону (початок, кінець) у даному масиві,

Приклад

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

Пояснення

(0, 2, 4, 1) додайте 1 до всіх цілих чисел у межах діапазону, оскільки це запит типу 0.

(1, 3, 5, 2) відніміть 2 від усіх цілих чисел у межах діапазону, оскільки це запит типу 1.

(0, 1, 4, 3) додайте 3 до всіх цілих чисел у межах діапазону, оскільки це запит типу 0.

Вивести змінений масив після виконання команд додавання та віднімання

 

Алгоритм друку модифікованого масиву після декількох запитів

  1. Ініціалізуйте масив з 0.
  2. Для кожного запиту
  3. Якщо запит типу полягає у додаванні значень, оновіть значення в лівій позиції-1, додавши значення k, а в правій позиції відніміть значення k.
  4. Якщо запит типу полягає у відніманні значень, оновіть значення в лівій позиції-1, віднявши значення k, а в правій позиції додайте значення k.
  5. Обхід масиву та додавання кожного попереднього значення до поточного значення масиву.
  6. Друк остаточного масиву.

Пояснення

Нам дається масив, спочатку всі значення в масиві дорівнюють 0. Нам також надається a q кількість запитів, запит буде двох типів, кожен запит містить, його тип, діапазон і число k. Якщо тип запиту дорівнює 0, ми додамо значення k до всіх цілих чисел, що входять в діапазон. Якщо нам задано тип запиту як 1, ми віднімемо значення k з усіх цілих чисел у межах діапазону. Після виконання всіх запитів ми надрукуємо отриманий масив.

За виконання цих операцій. Спочатку нам потрібно перевірити, який тип запиту нам заданий. Якщо запит першого типу, тоді ми додаємо значення k до початкової точки діапазону в масиві. Крім того, відніміть значення k з кінцевої точки діапазону масиву.

Ми зробимо протилежне раніше згаданій техніці. Якщо нам дано використовувати запит типу 1, в якому ми повинні відняти всі значення цілочисельного масиву в межах діапазону. Тоді ми віднімемо значення k від значення початкового діапазону масиву. Після цього додайте значення k до кінцевого індексу діапазону.

Для кожного із поданих запитів. Ми повинні виконати згадану техніку. Тоді ми будемо будувати масив, в якому ми додамо попереднє значення до поточного значення масиву. І збережіть суму до поточного значення. Або ми можемо сказати, що ми оновлюємо поточне значення масиву. Після побудови масиву ми будемо друкувати масив. Це буде бажаним результатом модифікованого масиву.

код

Код С ++ для друку модифікованого масиву після виконання команд додавання та віднімання

#include<iostream>
#include<stdio.h>
#include<string.h>

using namespace std;

void solveQuery(int arr[], int n, int T, int left, int right, int k)
{
    if (T == 0)
    {
        arr[left -1] += k;
        arr[right] += -k;
    }
    else
    {
        arr[left -1] += -k;
        arr[right] += k;
    }
    return;
}

void build(int arr[], int n)
{
    for (int i = 1; i < n; ++i)
        arr[i] += arr[i-1];

    return;
}

int main()
{
    int n = 5;
    int arr[n+1];

    memset(arr, 0, sizeof(arr));


    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 2, 4, 1);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 1, 3, 5, 2);

    //query, left, right, k(value which is to add or subtract.
    solveQuery(arr, n, 0, 1, 4, 3);

    build(arr, n);

    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}
3 4 2 2 -2

Код Java для друку модифікованого масиву після виконання команд додавання та віднімання

import java.util.Arrays;

class AdditionSubtractionQuery
{
    static void solveQuery(int arr[], int n, int T, int left, int right, int k)
    {
        if (T == 0)
        {
            arr[left -1] += k;
            arr[right] += -k;
        }
        else
        {
            arr[left -1] += -k;
            arr[right] += k;
        }
        return;
    }
    
    static void build(int arr[], int n)
    {
        for (int i = 1; i < n; ++i)
            arr[i] += arr[i-1];
    }
    
    public static void main(String arg[])
    {
        int n = 5;
        int arr[] = new int[n+1];
        Arrays.fill(arr, 0);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 2, 4, 1);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 1, 3, 5, 2);

        //query, left, right, k(value which is to add or subtract.
        solveQuery(arr, n, 0, 1, 4, 3);

        build(arr, n);

        for (int i = 0; i < n; ++i)
            System.out.print(arr[i]+" ");
    }
}
3 4 2 2 -2

Аналіз складності

Складність часу

O (q + n) де "Q" - кількість запитів, і "N" - кількість елементів у масиві. Оскільки спочатку ми виконуємо запити Q, які займають час O (1), а потім побудова масиву вимагає часу O (N).

Складність простору

О (п) де "N" - кількість елементів у масиві. Оскільки ми створили масив для виконання операцій. Складність простору лінійна.