అదనంగా మరియు వ్యవకలనం యొక్క ఆదేశాలను అమలు చేసిన తర్వాత సవరించిన శ్రేణిని ముద్రించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది ByteDance సిస్కో సిట్రిక్స్ ఫ్రీచార్జ్ HackerRank నాగరో ఒపేరా Teradata
అర్రే

మీకు పరిమాణం n యొక్క శ్రేణి ఇవ్వబడుతుంది, ప్రారంభంలో శ్రేణిలోని అన్ని విలువలు 0, మరియు ప్రశ్నలు. ప్రతి ప్రశ్నలో నాలుగు విలువలు, ప్రశ్న రకం, పరిధి యొక్క ఎడమ బిందువు, శ్రేణి యొక్క కుడి బిందువు మరియు సంఖ్య 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. టైప్ ప్రశ్న విలువలను జోడించాలంటే, విలువను k ని జోడించి ఎడమ -1 స్థానంలో అప్‌డేట్ చేయండి మరియు కుడి స్థానంలో k విలువను తీసివేయండి.
  4. టైప్ ప్రశ్న విలువలను తీసివేయడం అయితే, విలువను k ను తీసివేయడం ద్వారా ఎడమ -1 స్థానంలో విలువను నవీకరించండి మరియు కుడి స్థానంలో k విలువను జోడించండి.
  5. శ్రేణిలో ప్రయాణించి, ప్రతి మునుపటి విలువను శ్రేణి యొక్క ప్రస్తుత విలువకు జోడించండి.
  6. చివరి శ్రేణిని ముద్రించండి.

వివరణ

మనకు శ్రేణి ఇవ్వబడింది, ప్రారంభంలో, శ్రేణిలోని అన్ని విలువలు 0. మనకు కూడా a తో అందించబడుతుంది q ప్రశ్నల సంఖ్య, ప్రశ్న రెండు రకాలుగా ఉంటుంది, ప్రతి ప్రశ్నలో దాని రకం, పరిధి మరియు ఒక సంఖ్య k ఉంటాయి. ప్రశ్న యొక్క రకం 0 అయితే, మేము పరిధిలో వచ్చే అన్ని పూర్ణాంకాలకు k విలువను జోడిస్తాము. మనకు ప్రశ్న రకాన్ని 1 గా ఇస్తే, పరిధిలో ఉన్న అన్ని పూర్ణాంకాల నుండి k విలువను తీసివేస్తాము. అన్ని ప్రశ్నలను అమలు చేసిన తరువాత, మేము ఫలిత శ్రేణిని ముద్రించాము.

ఈ కార్యకలాపాలను నిర్వహించడానికి. మొదట మనకు ఏ రకమైన ప్రశ్న ఇవ్వబడుతుందో తనిఖీ చేయాలి. ప్రశ్న మొదటి రకం అయితే, మేము శ్రేణిలోని శ్రేణి యొక్క ప్రారంభ బిందువుకు k విలువను జోడిస్తాము. అలాగే, శ్రేణి యొక్క శ్రేణి యొక్క ముగింపు స్థానం నుండి k విలువను తీసివేయండి.

మేము ఇంతకుముందు చెప్పిన టెక్నిక్‌కు విరుద్ధంగా చేస్తాము. టైప్ 1 ప్రశ్నను ఉపయోగించమని మాకు ఇవ్వబడితే, పూర్ణాంక శ్రేణి యొక్క అన్ని విలువలను పరిధిలో తీసివేయాలి. అప్పుడు మేము శ్రేణి యొక్క ప్రారంభ శ్రేణి విలువ నుండి k విలువను తీసివేస్తాము. ఆ తరువాత, పరిధి యొక్క ఎండ్ పాయింట్ సూచిక వద్ద k విలువను జోడించండి.

ఇచ్చిన ప్రతి ప్రశ్నకు. మేము పేర్కొన్న సాంకేతికతను ప్రదర్శించాలి. అప్పుడు మేము శ్రేణిని నిర్మిస్తాము, దీనిలో మునుపటి విలువను శ్రేణి యొక్క ప్రస్తుత విలువకు జోడిస్తాము. మరియు మొత్తాన్ని ప్రస్తుత విలువకు నిల్వ చేయండి. లేదా మేము శ్రేణి యొక్క ప్రస్తుత విలువను అప్‌డేట్ చేస్తామని చెప్పవచ్చు. శ్రేణిని నిర్మించిన తరువాత, మేము శ్రేణిని ముద్రించాము. ఇది సవరించిన శ్రేణి యొక్క ఆశించిన ఫలితం అవుతుంది.

కోడ్

అదనంగా మరియు వ్యవకలనం యొక్క ఆదేశాలను అమలు చేసిన తర్వాత సవరించిన శ్రేణిని ముద్రించడానికి C ++ కోడ్

#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

అదనంగా మరియు వ్యవకలనం యొక్క ఆదేశాలను అమలు చేసిన తర్వాత సవరించిన శ్రేణిని ముద్రించడానికి జావా కోడ్

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” శ్రేణిలోని మూలకాల సంఖ్య. ఎందుకంటే మొదట మేము O (1) సమయం తీసుకునే Q ప్రశ్నలను నిర్వహిస్తాము మరియు తరువాత శ్రేణిని నిర్మించడానికి O (N) సమయం అవసరం.

అంతరిక్ష సంక్లిష్టత

పై) (ఇక్కడ “N” శ్రేణిలోని మూలకాల సంఖ్య. కార్యకలాపాలను నిర్వహించడానికి మేము శ్రేణిని సృష్టించాము కాబట్టి. స్థల సంక్లిష్టత సరళంగా ఉంటుంది.