Испис модификованог низа након операција повећања вишеструког опсега низа  


Ниво тешкоће Тежак
Често питани у Екпедиа Бесплатно гоогле Заиста Моонфрог Лабс Ола Цабс Куалтрицс
Ред Куери Проблем

Проблем „Испис модификованог низа након операција прираста вишеструког опсега низа“ наводи да сте добили цео број поредак и дати су 'к' бројеви упита. Такође је дата једна целобројна вредност „д“. Сваки упит садржи две целобројне вредности, почетну вредност и завршну вредност. Изјава о проблему тражи да се сазна да се све вредности у низу унутар датог опсега повећају за вредност „д“. Одштампајте модификовани низ.

Пример  

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

Објашњење

Након повећања са индекса (1,2), арр ће бити {2, 7, 3, 4, 7, 9}

Сада ће прираштај од индекса (3,5) арр постати {2, 7, 3, 6, 9, 11}

Поново ће пораст од индекса (4,5) заостатка бити {2, 7, 3, 6, 11, 13}

Сада ће прираштај од индекса (2,4) арр постати {2, 7, 5, 8, 13, 13}

Поново ће пораст од индекса (1,3) заостатка бити {2, 9, 7, 10, 13, 13}

 

Испис модификованог низа након операција повећања вишеструког опсега низаПин

Алгоритам за операције повећања опсега вишеструких поља  

  1. Прогласите низ исте величине као и дати низ.
  2. Пређите низ од 0 до укупног броја упита.
  3. Додајте дату вредност из низа који смо креирали у дати опсег. Проверите да ли је крајњи опсег датог упита мањи од дужине низа. Ако је тачно, смањите вредност „д“ из низа који смо креирали.
  4. Пређите преко датог низа и ажурирајте излазни низ додавањем тренутне и претходних вредности и датог низа.
  5. Одштампајте ажурирани низ.
Види такође
Подскуп са сумом дељивим са м

Објашњење

С обзиром на поредак of цео број и одређени број упита, сваки упит садржи почетни и завршни опсег и задату вредност. Морамо да додамо дату вредност свим бројевима од почетне до крајње тачке датог опсега. Створићемо низ упита. Два броја ће бити повезана са сваким низом упита. Створићемо додатни низ исте величине као и дужина датог низа. Извршићемо операције на овом низу, а затим ћемо их ажурирати на датом низу.

Сада покрећемо петљу до броја упита. Ажурираћемо излазни низ додавањем дате вредности d, на почетном индексу упита. Проверите да ли је крајња вредност упита мања од дужине низа. Ако се утврди да је тачно ако је тачно, смањите д у односу на претходно ажурирану вредност у излазном низу. Ово је како бисмо били сигурни да нећемо изаћи из опсега и вредности.

Сада ћемо ажурирати прву позицију датог низа на прву позицију излазног низа. Зато што ћемо прећи преко претходних вредности низа (или излаза) низа и тренутне вредности. Дакле, већ смо ажурирали прву вредност и сада прелазимо од прве позиције излазног низа до краја. Сабраћемо претходну и тренутну вредност и сачувати је у излазном низу. Затим копирајте ту вредност у одговарајуће позиције датог низа током обилажења. Одштампајте модификовани низ.

Види такође
Померите све негативне бројеве на почетак и позитивне да бисте их завршили са сталним додатним размаком

код  

Ц ++ код за испис модификованог низа након операција повећања вишеструког опсега низа

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

using namespace std;

struct query
{
    int start, end;
};

void incrementByD(int arr[], struct query q_arr[],int n, int m, int d)
{
    int sum[n];
    memset(sum, 0, sizeof(sum));

    for (int i = 0; i < m; i++)
    {
        sum[q_arr[i].start] += d;

        if ((q_arr[i].end + 1) < n)
            sum[q_arr[i].end + 1] -= d;
    }
    arr[0] += sum[0];
    for (int i = 1; i < n; i++)
    {
        sum[i] += sum[i - 1];
        arr[i] += sum[i];
    }
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = {2, 5, 1, 4, 7, 9};
    struct query q_arr[] = { { 1, 2 }, { 3, 5 },  {4,5 },
        { 2, 4 }, { 1, 3 }
    };
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = sizeof(q_arr) / sizeof(q_arr[0]);

    int d = 2;

    cout << "Original Array:\n";
    printArray(arr, n);

    incrementByD(arr, q_arr, n, m, d);

    cout << "\nModified Array:\n";
    printArray(arr, n);

    return 0;
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

Јава код за испис модификованог низа након операција повећања вишеструког опсега низа

class modifiedArray
{
    static class query
    {
        int start, end;

        query(int start, int end)
        {
            this.start = start;
            this.end = end;
        }
    }

    public static void incrementByD(int[] arr, query[] q_arr, int n, int m, int d)
    {
        int[] sum = new int[n];

        for (int i = 0; i < m; i++)
        {
            sum[q_arr[i].start] += d;

            if ((q_arr[i].end + 1) < n)
                sum[q_arr[i].end + 1] -= d;
        }
        arr[0] += sum[0];
        for (int i = 1; i < n; i++)
        {
            sum[i] += sum[i - 1];
            arr[i] += sum[i];
        }
    }

    public static void printArray(int[] arr, int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }

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

        int n = arr.length;
        int m = q_arr.length;
        int d = 2;
        System.out.println("Original Array:");
        printArray(arr, n);

        incrementByD(arr, q_arr, n, m, d);
        System.out.println("\nModified Array:");
        printArray(arr, n);
    }
}
Original Array:
2 5 1 4 7 9
Modified Array:
2 9 7 10 13 13

Анализа сложености  

Сложеност времена

 О (к + н) где „Н“ је број елемената у низу и „к ” је број упита. Будући да смо користили приступ попут префикса зброја, имамо линеарну временску сложеност.

Види такође
Проблем промене новца

Сложеност простора

 Он) где „Н“ је број елемената у низу.