সংযোজন এবং বিয়োগের কমান্ডগুলি কার্যকর করার পরে পরিবর্তিত অ্যারে মুদ্রণ করুন


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় ByteDance সিসকো Citrix ফ্রিচার্জ HackerRank নাগরো অপেরা তেরদাটা
বিন্যাস

আপনাকে আকারের একটি অ্যারে দেওয়া হবে, প্রাথমিকভাবে অ্যারের সমস্ত মান 0 এবং কোয়েরিগুলি হবে। প্রতিটি ক্যোয়ারিতে চারটি মান রয়েছে, ক্যোয়ারী টাইপের টাইপ করুন, রেঞ্জের বাম পয়েন্ট, একটি রেঞ্জের ডান পয়েন্ট এবং একটি সংখ্যা কে, আপনাকে নিম্নলিখিত ক্রিয়াকলাপ সম্পাদন করতে হবে।

যদি টি = 0, প্রদত্ত অ্যারেতে প্রদত্ত ব্যাপ্তির (শুরু, শেষ) এর মধ্যে পূর্ণসংখ্যার মান মান যোগ করে,

যদি টি = 1, প্রদত্ত অ্যারেতে প্রদত্ত ব্যাপ্তির (শুরু, শেষ) মধ্যে পূর্ণসংখ্যা থেকে মান কে বিয়োগ করে,

উদাহরণ

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 অবস্থানে মান আপডেট করুন এবং মান কে কে বিয়োগ করুন।
  4. যদি টাইপ ক্যোয়ারী মানগুলি বিয়োগ করতে হয় তবে মান k কে বিয়োগ করে বাম -1 অবস্থানে মান আপডেট করুন এবং ডান অবস্থানে মান কে যোগ করুন।
  5. অ্যারেটি অতিক্রম করুন এবং অ্যারের বর্তমান মানটিতে প্রতিটি পূর্ববর্তী মান যুক্ত করুন।
  6. চূড়ান্ত অ্যারে মুদ্রণ করুন।

ব্যাখ্যা

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

এই অপারেশনগুলি সম্পাদন করার জন্য। প্রথমে আমাদের কী ধরণের ক্যোয়ারী দেওয়া হয়েছে তা খতিয়ে দেখতে হবে। যদি কোয়েরিটি প্রথম প্রকারের হয় তবে আমরা অ্যারের রেঞ্জের প্রারম্ভিক বিন্দুতে মান k যুক্ত করি। এছাড়াও, অ্যারের সীমার শেষ বিন্দু থেকে মান কে বিয়োগ করুন।

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

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

কোড

সি ++ কোড সংযোজন এবং বিয়োগফলের আদেশগুলি কার্যকর করার পরে পরিবর্তিত অ্যারে প্রিন্ট করতে হবে

#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

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

সময় জটিলতা

ও (কিউ + এন) কোথায় "Q" এর প্রশ্নের সংখ্যা, এবং "এন" অ্যারেতে উপাদানগুলির সংখ্যা। কারণ প্রথমে আমরা প্রশ্ন অনুসন্ধান করি যা O (1) সময় নেয় এবং তারপরে অ্যারে তৈরি করতে ও (এন) সময় প্রয়োজন।

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। যেহেতু আমরা অপারেশনগুলি সম্পাদন করার জন্য একটি অ্যারে তৈরি করেছি। স্থান জটিলতা রৈখিক।