इसके अलावा और घटाव के आदेशों को निष्पादित करने के बाद संशोधित सरणी प्रिंट करें


कठिनाई स्तर मध्यम
में अक्सर पूछा ByteDance सिस्को Citrix स्वतंत्र प्रभार HackerRank नगरो संचालित Teradata
ऐरे

आपको एक आकार n दिया जाता है, प्रारंभ में सरणी के सभी मान 0 और प्रश्न होंगे। प्रत्येक क्वेरी में चार मान होते हैं, क्वेरी T का प्रकार, श्रेणी का बायाँ बिंदु, एक श्रेणी का सही बिंदु और एक नंबर k, आपको निम्नलिखित ऑपरेशन करने होंगे।

यदि T = 0, दिए गए सरणी में दिए गए सीमा (प्रारंभ, अंत) के भीतर सभी पूर्णांकों के लिए मान जोड़ें

यदि 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. हैं। हमें एक के साथ भी प्रदान किया गया है q प्रश्नों की संख्या, क्वेरी दो प्रकार की होगी, प्रत्येक क्वेरी में उसका प्रकार, श्रेणी और एक नंबर k होता है। यदि क्वेरी का प्रकार 0 है, तो हम रेंज में आने वाले सभी पूर्णांकों के लिए मान k जोड़ देंगे। यदि हमें 1 के रूप में क्वेरी का प्रकार दिया जाता है, तो हम सभी पूर्णांकों के मान को रेंज के भीतर घटा देंगे। सभी प्रश्नों को निष्पादित करने के बाद, हम उस परिणामी सरणी को प्रिंट करेंगे।

इन ऑपरेशनों को करने के लिए। पहले हमें यह जांचने की आवश्यकता है कि हमें किस प्रकार की क्वेरी दी गई है। यदि क्वेरी पहले प्रकार की है, तो हम सरणी में रेंज के शुरुआती बिंदु पर मूल्य 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) जहां 'क्यू' प्रश्नों की संख्या है, और "N" सरणी में तत्वों की संख्या है। क्योंकि पहले हम Q क्वेश्चन करते हैं जो O (1) टाइम लेते हैं और फिर ऐरे को बनाते समय O (N) टाइम की आवश्यकता होती है।

अंतरिक्ष जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। चूंकि हमने ऑपरेशन करने के लिए एक सरणी बनाई थी। अंतरिक्ष की जटिलता रैखिक है।