एकाधिक अ‍ॅरे श्रेणी वाढीव ऑपरेशन्सनंतर सुधारित अ‍ॅरे मुद्रित करा


अडचण पातळी हार्ड
वारंवार विचारले यामध्ये फ्रीचार्ज Google खरंच मूनफ्रोग लॅब ओला कॅब गुण
अरे क्वेरी समस्या

"मल्टीपल अ‍ॅरे रेंज इनक्रिमेंट ऑपरेशन्स नंतर मॉडिफाईड अ‍ॅरे प्रिंट करा" ही समस्या आपल्याला सांगते की पूर्णांक अॅरे आणि 'क्यू' क्वेरी संख्या दिली आहेत. एक पूर्णांक मूल्य "d" देखील दिले आहे. प्रत्येक क्वेरीमध्ये दोन पूर्णांक असतात, प्रारंभ मूल्य आणि अंतिम मूल्य प्रॉब्लेम स्टेटमेंट दिलेल्या रेंजमधील अ‍ॅरे मधील सर्व व्हॅल्यूज “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 be असेल

आता निर्देशांकातील वाढ (2,4) एरर ची वाढ {2, 7, 5, 8, 13, 13} होईल

अनुक्रमणिकेतून पुन्हा वाढ (1,3) एआर {2, 9, 7, 10, 13, 13 be असेल

 

एकाधिक अ‍ॅरे श्रेणी वाढीव ऑपरेशन्सनंतर सुधारित अ‍ॅरे मुद्रित करा

एकाधिक अ‍ॅरे श्रेणी वाढीच्या क्रियांसाठी अल्गोरिदम

  1. दिलेल्या अ‍ॅरेच्या आकाराप्रमाणे अ‍ॅरे घोषित करा.
  2. अ‍ॅरे 0 वरून एकूण प्रश्नांपर्यंत जा.
  3. आम्ही दिलेल्या श्रेणीमध्ये तयार केलेल्या अ‍ॅरेमध्ये दिलेली मूल्य जोडा. दिलेल्या क्वेरीची अंतिम श्रेणी अ‍ॅरेच्या लांबीपेक्षा कमी आहे का ते तपासा. सत्य असल्यास, तयार केलेल्या अ‍ॅरे वरुन “d” व्हॅल्यू कमी करा.
  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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

 ओ (क्यू + एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या आणि “प्रश्न ” क्वेरींची संख्या आहे. प्रीफिक्स बेरीज सारख्या पध्दतीचा वापर केल्यामुळे आपल्यात रेषात्मक अवघडपणा आहे.

स्पेस कॉम्प्लेक्सिटी

 O (n) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या.