আপডেট ছাড়াই ব্যাপ্তির যোগফলগুলি


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় কালো শিলা জিই হেলথকেয়ার মুনফ্রোগ ল্যাব সংক্ষেপ ট্যাক্সি4 সুরক্ষা Twilio
বিন্যাস লারসেন ও টুব্রো প্রশ্ন সমস্যা

সমস্যা বিবৃতি

"আপডেট ছাড়া রেঞ্জের যোগফলগুলি" সমস্যাটি জানিয়েছে যে আপনার একটি রয়েছে বিন্যাস of পূর্ণসংখ্যার এবং একটি পরিসীমা। সমস্যা বিবৃতি প্রদত্ত ব্যাপ্তির মধ্যে থাকা সমস্ত উপাদানের যোগফল খুঁজে পেতে বলে।

উদাহরণ

arr[]={10, 9, 8, 7, 6}

Query: {(0, 4), (1, 3)}
40 24

ব্যাখ্যা

(0, 4) সহ সমুদ্রের মধ্যে সমস্ত সংখ্যার যোগফল 40 এবং সমষ্টিগত (1, 3) এর মধ্যে সমস্ত সংখ্যার যোগফল 24 হয়।

আপডেট ছাড়াই ব্যাপ্তির যোগফলগুলি

 

অ্যালগরিদম

  1. প্রদত্ত অ্যারের মতো আকারের একটি অ্যারের যোগফল তৈরি করুন।
  2. প্রদত্ত অ্যারে পেরিয়ে যান এবং যোগফলের পূর্ববর্তী উপাদানটির যোগফল এবং অ্যারের বর্তমান উপাদানটিকে যোগ করে যোগফলের মধ্যে সঞ্চয় করে রাখুন।
  3. প্রতিটি ক্যোয়ারির জন্য, যদি বাম 0 এর সমান হয়, তবে যোগফলটি [ডান] ফিরিয়ে দিন,
  4. অন্যথায় যোগফলটি [ডান] - জরিমানা [বাম - 1] প্রদান করুন।

ব্যাখ্যা

আমরা পূর্ণসংখ্যার একটি অ্যারে এবং একটি ব্যাপ্তি দিয়েছি, প্রতিটি প্রশ্নের জন্য আমাদের দেওয়া রেঞ্জের মধ্যে থাকা সমস্ত উপাদানের যোগফল জানতে চাওয়া হয়েছে। প্রতিটি প্রশ্নের মধ্যে একটি ব্যাপ্তির শুরু এবং শেষ পয়েন্ট হিসাবে একটি পরিসীমা থাকে। এই প্রশ্নটিতে কোনও আপডেট ক্যোয়ারী জড়িত না। এর অর্থ ক্যোয়ারির উত্তর সন্ধান করার সময় কোনও জিনিস আপডেট করার দরকার নেই। আমরা কেবল প্রদত্ত অ্যারেটি তৈরি করব যাতে 0 সূচক থেকে বর্তমান সূচক পর্যন্ত সমস্ত উপাদানের যোগফল অন্তর্নির্মিত অ্যারের আইথ অবস্থানে থাকে। এইভাবে, প্রতিটি প্রশ্নের ও (1) এ ও (এন) এর অতিরিক্ত স্থান সহ সমাধান করা হবে।

আমরা তৈরি করা অঙ্কটি তৈরি করব। এই যোগফলে, 0 থেকে i পর্যন্ত উপাদানগুলির যোগফল যোগফলের আইথ অবস্থানে সংরক্ষণ করা হবে। আমরা এটিকে গণনা করব কারণ আমরা যোগআরারের পূর্ববর্তী মান এবং প্রদত্ত অ্যারের বর্তমান মান যুক্ত করব এবং এটি ট্র্যাভারিংয়ের সময় যোগফলের বর্তমান সূচী অবস্থানে সংরক্ষণ করব। সুতরাং যখন কেউ জিজ্ঞাসা করলেন যে এই পজিশনে সমস্ত সংখ্যার যোগফল কী, তখন আমাদের কেবল প্রতিটি অনন্য অ্যারে উপাদানগুলির জন্য সেই অবস্থানটির মানটি ফিরিয়ে নেওয়া উচিত।

আমরা যখন কোনও ব্যাপ্তিকে সমন্বিত একটি কোয়েরি পেয়েছি এবং যদি আমরা সীমাটির বাম বা প্রারম্ভিক বিন্দু 0 এর সমান দেখতে পাই তবে আমরা কেবল যোগফল [ডান] এর মানটি ফিরিয়ে দেব যা আমরা উপরে আলোচনা করেছি, বাম পরিসরটি হ'ল 0 এর সমান নয় আমরা যোগফল [ডান] এবং যোগআরয়ের [বাম -1] এর পার্থক্য ফিরিয়ে দেব। এগুলির উত্তর প্রয়োজন হবে। এই পদ্ধতিটি আমরা ব্যবহার করি এমন একটি সহজ উপায় ডায়নামিক প্রোগ্রামিং.

কোড

আপডেট ছাড়াই ব্যাপ্তির যোগফলের প্রশ্নের জন্য সি ++ কোড

#include<iostream>

using namespace std;

void buildSumArray(int arr[], int n, int sumArray[])
{
    sumArray[0] = arr[0];
    for (int i = 1; i < n; i++)
        sumArray[i] = arr[i] + sumArray[i - 1];
}

int solveQuery(int left, int right, int sumArray[])
{
    if (left == 0)
        return sumArray[right];

    return sumArray[right] - sumArray[left -1];
}

int main()
{
    int arr[] = {10,9,8,7,6};
    int n = sizeof(arr)/sizeof(arr[0]);

    int sumArray[n];

    buildSumArray(arr, n, sumArray);

    cout << solveQuery(0, 4, sumArray) << endl;
    cout << solveQuery(1, 3, sumArray) << endl;

    return 0;
}
40
24

আপডেট ছাড়াই রেঞ্জের যোগফলগুলির জন্য জাভা কোড

class RangeQueriesSum
{
    public static void buildSumArray(int arr[], int n, int sumArray[])
    {
        sumArray[0] = arr[0];
        for (int i = 1; i < n; i++)
            sumArray[i] = arr[i] + sumArray[i - 1];
    }

    public static int solveQuery(int left, int right, int sumArray[])
    {
        if (left == 0)
            return sumArray[right];

        return sumArray[right] - sumArray[left -1];
    }

    public static void main(String[] args)
    {
        int arr[] = {10,9,8,7,6};
        int n = arr.length;

        int sumArray[] = new int[n];

        buildSumArray(arr, n, sumArray);
        System.out.println(solveQuery(0, 4, sumArray));
        System.out.println(solveQuery(1, 3, sumArray));
    }
}
40
24

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন + কিউ),  কারণ আমাদের যোগফলের অঙ্কের জন্য ও (এন) এবং তারপরে প্রতিটি প্রশ্নের জন্য ও (1) সময় প্রয়োজন।

স্পেস জটিলতা ity

এখানে প্রদত্ত পদ্ধতির ক্ষেত্রে, 0 থেকে i পর্যন্ত উপাদানগুলির যোগফল সংরক্ষণ করার জন্য আমরা একটি নতুন অ্যারে যোগফল তৈরি করেছি। সুতরাং এই পদ্ধতির প্রয়োজন চালু) স্থান। তবে আমরা মূল অ্যারেটিও সংশোধন করতে পারতাম। তারপরে স্পেস জটিলতা কমে যেতে পারত ধ্রুবককে।