बहु प्रतिस्थापन और उत्पाद के लिए ऐरे प्रश्न  


कठिनाई स्तर कठिन
में अक्सर पूछा ताल भारत डीई शॉ Expedia गूगल
ऐरे क्वेरी की समस्या

समस्या "एरियर क्वेरीज़ फॉर मल्टीप्ली, रिप्लेसमेंट एंड प्रोडक्ट" में कहा गया है कि आपको ए सरणी of पूर्णांक और तीन प्रकार के प्रश्न होंगे, जहां आपको निम्नलिखित प्रकार के प्रश्नों को हल करना होगा:

टाइप 1: तीन वैल्यू लेफ्ट, राइट और एक नंबर X होगी। इस तरह के क्वैरी में, आपको एरे के प्रत्येक एलिमेंट को रेंज में वैल्यू X के लिए (लेफ्ट, राइट) को इनक्लूसिवली गुणा करना होगा।

टाइप 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 के भीतर सभी तत्वों के उत्पाद के बाद

टाइप 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 के भीतर सभी तत्वों के उत्पाद के बाद

आउटपुट ⇒ 3, तो कुल 3 अनुगामी शून्य होंगे जो हमने टाइप 3 प्रश्नों में पाए हैं, इसलिए यह मुद्रित है।

गुणन, प्रतिस्थापन और उत्पाद के लिए ऐरे प्रश्नपिन

 

कलन विधि  

  1. दो सरणियों को इस तरह घोषित करें कि दोनों सारणियां क्रमशः संख्या 2 और 5 के सापेक्ष अनुगामी शून्य की संख्या को संग्रहित करेंगी।
  2. यदि हम टाइप 1 के लिए कॉल कर रहे हैं, तो 2 और 5 के संदर्भ में, एक्स के अनुगामी शून्य प्राप्त करें।
  3. किसी दिए गए सीमा के भीतर सरणी के माध्यम से पार। एक मान X के साथ प्रत्येक संख्या को गुणा करें। इसके साथ ही, 2 और 5 के गुणकों के लिए शून्य का मान स्टोर करें, जो इसके लिए बनाए गए सरणी में है। ज़ीरोइनटू और जीरोइनफाइव.
  4. यदि हम टाइप 2 के लिए कॉल कर रहे हैं, तो 2 और 5 के संदर्भ में, फिर से वाई के अनुगामी शून्य प्राप्त करें।
  5. श्रेणी के पहले स्थान पर वाई को स्टोर करें, दूसरे पर 2 वाई और इसी तरह। इसके साथ ही जीरो को ट्रेलिंग जीरो की गिनती स्टोर करें।
  6. और टाइप 3 के लिए, सभी मानों का योग प्राप्त करें जो कि zeroesInTwo और zeroesInFive में एक श्रेणी में हैं, और दो में शून्य की गिनती या शून्य में गिनती की न्यूनतम संख्या का पता लगाएं।
  7. मूल्य में प्रिंट करें।

व्याख्या  

हमें हल करने के लिए एक पूर्णांक सरणी और तीन प्रकार की क्वेरी दी जाती है। प्रश्नों में से एक का कहना है कि आपको सीमा के भीतर कुछ संख्या को गुणा करना होगा। दूसरा कहता है कि आपको कुछ नंबर बदलने होंगे। आखिरी कहता है कि आपको रेंज के भीतर संख्याओं का उत्पाद ढूंढना है। फिर हमने प्रत्येक क्वेरी को करने के लिए अलग-अलग तीन कार्य किए हैं जो क्रमशः प्रत्येक क्वेरी के लिए अपना भाग करते हैं। फिर हम अनुगामी शून्य का पता लगाएंगे। उसके लिए हमने दो सरणियाँ बनाई हैं एक 2 के संदर्भ में है, और दूसरी 5 के संदर्भ में है।

यह भी देखें
अनोखा बाइनरी सर्च ट्रीज़

पहले प्रकार की क्वेरी को हल करने के लिए, हमें शुरुआती बिंदु और एक समाप्ति बिंदु के संदर्भ में एक संख्या एक्स और एक सीमा दी जाएगी। पता लगाने के लिए ट्रेलिंग जीरो जो हो सकते हैं। हम यह पता लगाएंगे कि क्या दिए गए नंबर में वह अनुगामी शून्य है। फिर इन अनुगामी शून्य की गिनती प्राप्त करें। यही बात पांच के संदर्भ में शून्य के साथ करना है। हम रेंज के शुरुआती बिंदु से लेकर रेंज के अंतिम बिंदु तक सरणी को पार कर रहे हैं। फिर हम ट्रैवर्स करते समय प्रत्येक संख्या के साथ मूल्य X को गुणा करेंगे। हम साथ-साथ उस ऐरे पर जोड़ को भी जोड़ेंगे जो हम ज़ीरो स्टोर करने के लिए बनाते हैं। यही काम टाइप 2 क्वेरी में करना है, हमें बस दिए गए नंबर से प्रत्येक तत्व को श्रृंखला के रूप में बदलना होगा।

टाइप थ्री क्वेरी को हल करने के लिए, हम का मान सेट करेंगे समऑफ टूस और सारांश 0. हम जिस समर में बना है उसका मान जमा करेंगे। तब हम समऑफ़वॉश और समऑफ़ फ़ाइव का न्यूनतम पता लगा लेंगे। वह आवश्यक और अंतिम उत्तर होगा जो हम लौट रहे हैं।

कोड  

गुणा, प्रतिस्थापन और उत्पाद के लिए ऐरे प्रश्न के लिए C ++ में कार्यान्वयन

#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

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

समय जटिलता

पर) जहां "N" सरणी में तत्वों की संख्या है। प्रत्येक क्वेरी के लिए O (N) समय की आवश्यकता होती है क्योंकि हमें हमें दी गई पूरी सीमा को पार करना होगा।

यह भी देखें
पहले लापता पॉजिटिव

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

पर) जहां "N" सरणी में तत्वों की संख्या है। चूंकि हमने इनपुट के अलावा दो सरणियों का निर्माण किया है, एल्गोरिथ्म में रैखिक अंतरिक्ष जटिलता है।