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


কাঠিন্য মাত্রা কঠিন
প্রায়শই জিজ্ঞাসা করা হয় ক্যাডেন্স ইন্ডিয়া ডিই শ এক্সপিডিয়া গুগল
বিন্যাস প্রশ্ন সমস্যা

"গুণ, প্রতিস্থাপন এবং পণ্যের জন্য অ্যারে ক্যোয়ারী" সমস্যাটি আপনাকে জানিয়েছে যে আপনাকে একটি দেওয়া হয়েছে বিন্যাস of পূর্ণসংখ্যা এবং এখানে তিন ধরণের ক্যোয়ারী থাকবে, যেখানে আপনাকে নিম্নলিখিত ধরণের প্রশ্নের সমাধান করতে হবে:

টাইপ 1: তিনটি বাম, ডান এবং একটি সংখ্যা এক্স থাকবে this এই ধরণের ক্যোয়ারিতে আপনাকে অ্যারের প্রতিটি উপাদানকে সমেত (বাম, ডান) রেঞ্জের মান XNUMX দিয়ে গুণ করতে হবে।

প্রকার 2: এটিতে তিনটি মান বামে রয়েছে, ডানদিকে পরিসীমা হিসাবে। আপনাকে প্রদত্ত রেঞ্জের উপাদানগুলি Y, 2Y, 3Y, এবং আরও কিছু দিয়ে প্রতিস্থাপন করতে হবে।

প্রকার 3: একটি পরিসীমা হিসাবে বাম এবং ডানদিকে দুটি মান থাকবে। আপনাকে প্রদত্ত ব্যাপ্তির মধ্যে থাকা সমস্ত উপাদানগুলির পণ্যটি সন্ধান করতে হবে। যেহেতু সংখ্যাটি বড় হতে পারে। আপনাকে সমস্ত টাইপ 3 ক্যোয়ারীতে মোট চলন্ত শূন্যের সংখ্যা গণনা করতে হবে।

উদাহরণ

arr[] = {1, 2, 3, 4, 5}
Query: { (3,2,5), (3,4,5), (2,1,3,1), (1,4,5,10), (3,2,4)}
3

ব্যাখ্যা

টাইপ 3 (2, 5), 2 এবং 5 2 3 * 4 * 5 * 120 = XNUMX এর মধ্যে থাকা সমস্ত উপাদানের পণ্য পরে

টাইপ 3 (3, 5), 3 এবং 5 ⇒ 3 * 4 * 5 = 60 এর মধ্যে থাকা সমস্ত উপাদানের পণ্য পরে

টাইপ 2 (1, 3, 1), প্রতিটি উপাদানকে y, 2y এবং 3y এবং এরপরে 1 থেকে 3 এর মধ্যে প্রতিস্থাপনের পরে

টাইপ 1 (4, 5, 10), প্রতিটি উপাদান 10 থেকে 4 এর মধ্যে 5 দিয়ে গুণিত করুন

টাইপ 3 (2, 4), 3 এবং 5 2 3 * 40 * 240 = XNUMX এর মধ্যে থাকা সমস্ত উপাদানগুলির পণ্যের পরে

আউটপুট ⇒ 3, সুতরাং আমরা টাইপ 3 কোয়েরিতে মোট 3 টি পিছনে জিরো থাকব, তাই এটি মুদ্রিত হবে।

গুণ, প্রতিস্থাপন এবং পণ্যের জন্য অ্যারে ক্যোয়ারী

 

অ্যালগরিদম

  1. দুটি অ্যারে এমনভাবে ঘোষণা করুন যে উভয় অ্যারে যথাক্রমে 2 এবং 5 সংখ্যার সাথে সম্পর্কিত ট্রেলিং শূন্যের সংখ্যা সংরক্ষণ করবে।
  2. আমরা যদি টাইপ 1 এর জন্য কল দিই, তবে 2 এবং 5 এর শর্তে এক্সের অনুবর্তনকারী শূন্যগুলি পান।
  3. প্রদত্ত ব্যাপ্তির মধ্যে অ্যারের মধ্য দিয়ে যান। প্রতিটি সংখ্যাকে একটি মানের এক্স দিয়ে গুণিত করুন Sim একই সাথে শূন্যের মানটি 2 এবং 5 এর একাধিক হিসাবে আমাদের জন্য তৈরি অ্যারেতে সংরক্ষণ করুন জেরোজআইনটো এবং zeroesInFive.
  4. আমরা যদি টাইপ 2 এর জন্য কল দিই, আবার 2 এবং 5 এর দিক দিয়ে Y এর পিছনের শূন্যগুলি পান।
  5. রেঞ্জের প্রথম অবস্থানে ওয়াই সংরক্ষণ করুন, দ্বিতীয় দিকে 2Y এবং আরও কিছু। একই সাথে শূন্য আইএনটিও এবং জিরোআইনফাইভের পিছনে শূণ্যের গণনা সংরক্ষণ করুন।
  6. এবং টাইপ 3 এর জন্য, জিরোআইএনটিও এবং জিরোআইনফাইভে একটি পরিসরে থাকা সমস্ত মানগুলির যোগফল পান এবং দুটিতে শূন্যের গণনা বা পাঁচটিতে শূন্যের গণনা সন্ধান করুন।
  7. যোগফলটি মুদ্রণ করুন।

ব্যাখ্যা

আমাদের সমাধানের জন্য একটি পূর্ণসংখ্যা অ্যারে এবং তিন ধরণের ক্যোয়ারী দেওয়া হয়। প্রশ্নের মধ্যে একটি বলেছে যে আপনাকে ব্যাপ্তির মধ্যে কিছু সংখ্যার গুণ করতে হবে। অন্যটি বলে যে আপনাকে কিছু নম্বর প্রতিস্থাপন করতে হবে। শেষটি বলে যে আপনাকে সীমার মধ্যে সংখ্যার পণ্যটি খুঁজে বের করতে হবে। তারপরে প্রতিটি প্রশ্নের প্রতিটি সম্পাদনের জন্য আমরা পৃথকভাবে তিনটি ফাংশন তৈরি করেছি যা প্রতিটি প্রশ্নের জন্য যথাক্রমে তাদের অংশ সম্পাদন করে। তারপরে আমরা পেছনের শূন্যগুলি খুঁজে বের করব। তার জন্য আমরা দুটি অ্যারে তৈরি করেছিলাম একটি 2 এর শর্তে এবং অন্যটি 5 এর শর্তে।

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

টাইপ তিনটি ক্যোয়ারী সমাধান করার জন্য, আমরা এর মান সেট করব যোগফল এবং যোগফল to 0. আমরা ভেরিয়েবলের মধ্যে আমরা SumOfTwos এবং SumOfFives তৈরি করে মান সংরক্ষণ করব। তারপরে আমরা সর্বনিম্ন SumOfTwos এবং SumOfFives সন্ধান করব। এটি প্রয়োজনীয় এবং চূড়ান্ত উত্তর হবে আমরা ফিরে আসব।

কোড

গুণমান, প্রতিস্থাপন এবং পণ্যের জন্য অ্যারে প্রশ্নের জন্য সি ++ তে বাস্তবায়ন

#include<vector>
#include<iostream>

using namespace std;

vector<int> zeroesInTwo(1000,0);

vector<int> zeroesInFive(1000,0);

int sum = 0;

int getTwosZeroes(int val)
{
    int count = 0;
    while (val % 2 == 0 && val != 0)
    {

        val = val / 2;
        count++;
    }

    return count;
}

int getFivesZeroes(int val)
{
    int count = 0;
    while (val % 5 == 0 && val != 0)
    {

        val = val / 5;
        count++;
    }

    return count;
}

void type1(int arr[],int ql, int qr, int x)
{
    int twoCount = getTwosZeroes(x);
    int fiveCount = getFivesZeroes(x);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = arr[i] * x;

        zeroesInTwo[i] += twoCount;
        zeroesInFive[i] += fiveCount;
    }
}

void type2(int arr[], int ql, int qr, int y)
{
    int twoCount = getTwosZeroes(y);
    int fiveCount = getFivesZeroes(y);

    for (int i = ql - 1; i < qr; i++)
    {
        arr[i] = (i - ql + 2) * y;

        zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
        zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
    }
}

void type3(int arr[],int ql, int qr)
{
    int sumtwos = 0;
    int sumfives = 0;

    for (int i = ql - 1; i < qr; i++)
    {
        sumtwos += zeroesInTwo[i];
        sumfives += zeroesInFive[i];
    }
    sum += min(sumtwos, sumfives);

}

int main()
{
    int arr[]= {1,2,3,4,5};

    int n=sizeof(arr)/sizeof(arr[0]);

    for (int i = 0; i < n; i++)
    {
        zeroesInTwo[i] = getTwosZeroes(arr[i]);
        zeroesInFive[i] = getFivesZeroes(arr[i]);
    }
    type3(arr,2,5);
    type3(arr,4,5);

    type2(arr,1,3,1);
    type1(arr,4,5,10);

    type3(arr,2,4);

    cout << sum << endl;
    return 0;
}
3

গুণে, প্রতিস্থাপন এবং পণ্যের জন্য অ্যারে প্রশ্নের জন্য জাভাতে বাস্তবায়ন

import java.util.*;

class type123
{
    private static int zeroesInTwo[]=new int[1000];

    private static int zeroesInFive[]=new int[1000];



    private static int sum = 0;

    private static int getTwosZeroes(int val)
    {
        int count = 0;
        while (val % 2 == 0 && val != 0)
        {

            val = val / 2;
            count++;
        }

        return count;
    }

    private static int getFivesZeroes(int val)
    {
        int count = 0;
        while (val % 5 == 0 && val != 0)
        {

            val = val / 5;
            count++;
        }

        return count;
    }

    private static void type1(int arr[],int ql, int qr, int x)
    {
        int twoCount = getTwosZeroes(x);
        int fiveCount = getFivesZeroes(x);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = arr[i] * x;

            zeroesInTwo[i] += twoCount;
            zeroesInFive[i] += fiveCount;
        }
    }

    private static void type2(int arr[], int ql, int qr, int y)
    {
        int twoCount = getTwosZeroes(y);
        int fiveCount = getFivesZeroes(y);

        for (int i = ql - 1; i < qr; i++)
        {
            arr[i] = (i - ql + 2) * y;

            zeroesInTwo[i] = getTwosZeroes(i - ql + 2) + twoCount;
            zeroesInFive[i] = getFivesZeroes(i - ql + 2) + fiveCount;
        }
    }

    private static void type3(int arr[],int ql, int qr)
    {
        int sumtwos = 0;
        int sumfives = 0;

        for (int i = ql - 1; i < qr; i++)
        {
            sumtwos += zeroesInTwo[i];
            sumfives += zeroesInFive[i];
        }
        sum += Math.min(sumtwos, sumfives);

    }

    public static void main(String []args)
    {
        int arr[]= {1,2,3,4,5};

        int n=arr.length;

        Arrays.fill(zeroesInTwo,0);

        Arrays.fill(zeroesInFive,0);

        for (int i = 0; i < n; i++)
        {
            zeroesInTwo[i] = getTwosZeroes(arr[i]);
            zeroesInFive[i] = getFivesZeroes(arr[i]);
        }

        type3(arr,2,5);
        type3(arr,4,5);

        type2(arr,1,3,1);
        type1(arr,4,5,10);

        type3(arr,2,4);

        System.out.println(sum);

    }
}
3

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

সময় জটিলতা

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

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

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