कई ऐरे रेंज इंक्रीमेंट ऑपरेशंस के बाद संशोधित एरे को प्रिंट करें  


कठिनाई स्तर कठिन
में अक्सर पूछा Expedia स्वतंत्र प्रभार गूगल वास्तव में मूनफ्रॉग लैब्स ओला कैब Qualtrics
ऐरे क्वेरी की समस्या

समस्या "प्रिंट सरणी संशोधित कई सरणी रेंज वेतन वृद्धि संचालन के बाद" बताता है कि आपको एक दिया जाता है पूर्णांक सरणी और 'q' प्रश्नों की संख्या दी गई है। एक पूर्णांक मान "डी" भी दिया जाता है। प्रत्येक क्वेरी में दो पूर्णांक होते हैं, आरंभिक मान और एक समाप्ति मान। समस्या का विवरण मान "d" द्वारा दी गई सीमा के भीतर सरणी के सभी मूल्यों को बढ़ाने के लिए कहता है। संशोधित सरणी मुद्रित करें।

उदाहरण  

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क्वेरी के शुरुआती सूचकांक पर। जांचें कि क्वेरी का अंतिम मान सरणी की लंबाई से कम है या नहीं। यदि यह सत्य पाया जाता है तो सही है तो आउटपुट सरणी में पहले से अद्यतन मान से d घटाएं। यह सुनिश्चित करने के लिए है कि हम सीमा और मूल्यों से बाहर नहीं जाएंगे।

अब, हम दिए गए सरणी की पहली स्थिति को आउटपुट सरणी पहली स्थिति में अद्यतन करने जा रहे हैं। क्योंकि हम सम (या आउटपुट) एरे के पिछले मानों और वर्तमान मूल्य को पार करने जा रहे हैं। इसलिए हमने पहले से ही पहले मूल्य को अपडेट किया और अब आउटपुट सरणी की पहली स्थिति से अंत तक पार किया। हम पिछले और वर्तमान मूल्य को जोड़ते हैं और इसे आउटपुट सरणी में संग्रहीत करते हैं। फिर उस मान को ट्रैवर्स करते समय दिए गए सरणी के संबंधित पदों पर कॉपी करें। संशोधित सरणी मुद्रित करें।

यह भी देखें
लगातार सभी नकारात्मक नंबरों को स्थानांतरित करें और लगातार अतिरिक्त स्थान के साथ समाप्त करने के लिए सकारात्मक

कोड  

C ++ कोड कई ऐरे रेंज इंक्रीमेंट ऑपरेशंस के बाद संशोधित एरे को प्रिंट करने के लिए

#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

जटिलता विश्लेषण  

समय जटिलता

 O (q + n) जहां "N" सरणी में तत्वों की संख्या है और "क्यू" प्रश्नों की संख्या है। चूंकि हमने उपसर्ग योग की तरह एक दृष्टिकोण का उपयोग किया है, इसलिए हमारे पास रैखिक समय की जटिलता है।

यह भी देखें
सिक्का बदलें समस्या

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

 पर) जहां "N" सरणी में तत्वों की संख्या है।