استعلامات صفيف لمضاعفة الاستبدالات والمنتج


مستوى الصعوبة الثابت
كثيرا ما يطلب في إيقاع الهند دي شو اكسبيديا جوجل
مجموعة مشكلة الاستعلام

توضح مشكلة "Array Queries for الضرب والاستبدال والمنتج" أنك تحصل على ملف مجموعة of عدد صحيح وستكون هناك ثلاثة أنواع من الاستعلامات ، حيث يتعين عليك حل النوع التالي من الاستعلامات:

النوع 1: ستكون هناك ثلاث قيم يسار ويمين ورقم X. في هذا النوع من الاستعلام ، عليك مضاعفة كل عنصر من عناصر المصفوفة في القيمة X في النطاق (يسار ، يمين) بشكل شامل.

النوع 2: يتكون من ثلاث قيم يسارًا ويمينًا كنطاق. يجب عليك استبدال العناصر الموجودة في النطاق المحدد بالأرقام Y و 2 Y و 3 Y وما إلى ذلك.

النوع 3: ستكون هناك قيمتان على اليسار واليمين كنطاق. عليك أن تجد حاصل ضرب كل العناصر ضمن النطاق المحدد. نظرًا لأن الرقم يمكن أن يكون كبيرًا. يجب عليك حساب العدد الإجمالي للأصفار اللاحقة في جميع استعلامات Type3.

مثال

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 ، فاحصل على الأصفار اللاحقة لـ X بدلالة 2 و 5.
  3. اجتياز المصفوفة داخل نطاق معين. اضرب كل رقم بقيمة X. في نفس الوقت ، قم بتخزين قيمة الأصفار كمضاعفات 2 و 5 في المصفوفة التي أنشأناها من أجل الأصفار في اثنين و الأصفار في خمسة.
  4. إذا كنا ندعو إلى النوع 2 ، فاحصل مرة أخرى على الأصفار اللاحقة لـ Y ، بدلالة 2 و 5.
  5. قم بتخزين Y في الموضع الأول من النطاق ، 2Y في الثانية وهكذا. قم بتخزين عدد الأصفار اللاحقة في نفس الوقت إلى الأصفار في اثنين وأصفار إن فايف.
  6. وبالنسبة للنوع 3 ، احصل على مجموع كل القيم الموجودة في نطاق مكون من أصفار في اثنين وأصفار إن فايف ، واكتشف الحد الأدنى لعدد الأصفار في اثنين أو عدد الأصفار في خمسة.
  7. اطبع القيمة في المجموع.

تفسير

لدينا مصفوفة عدد صحيح وثلاثة أنواع من الاستعلامات لحلها. يقول أحد الاستعلامات أنه يجب عليك مضاعفة بعض الأرقام داخل النطاق. يقول الآخر أنه يجب عليك استبدال بعض الأرقام. يقول آخر واحد أنه يجب عليك العثور على حاصل ضرب الأرقام داخل النطاق. ثم لإجراء كل من الاستعلامات ، قمنا بعمل الوظائف الثلاث بشكل منفصل والتي تؤدي دورها لكل استعلام على التوالي. ثم سنكتشف الأصفار اللاحقة. لذلك أنشأنا مصفوفتين أحدهما بدلالة 2 والآخر بدلالة 5.

لحل النوع الأول من الاستعلام ، سنحصل على رقم X ونطاق من حيث نقطة البداية ونقطة النهاية. لمعرفة الأصفار اللاحقة التي يمكن أن تحدث. سنكتشف ما إذا كان الرقم المحدد يحتوي على تلك الأصفار اللاحقة. ثم احصل على عدد هذه الأصفار اللاحقة. نفس الشيء يتعلق بالأصفار بدلالة خمسة. سنقوم باجتياز المصفوفة ، من نقطة بداية النطاق إلى نقطة نهاية النطاق. ثم سنضرب القيمة X في كل رقم أثناء العبور. سنقوم أيضًا بإجراء الإضافة في نفس الوقت على المصفوفة التي أنشأناها لتخزين الأصفار. نفس الشيء هو القيام به في استعلام من النوع 2 ، نحتاج فقط إلى استبدال كل عنصر بالرقم المحدد ، في شكل سلسلة.

لحل استعلام النوع الثالث ، سنقوم بتعيين قيمة مجموع و سوموفيفيفز إلى 0. سنقوم بتخزين القيمة في المتغير الذي أنشأناه sumOfTwos و sumOfFives. ثم سنكتشف الحد الأدنى من sumOfTwos و sumOfFives. ستكون هذه هي الإجابة المطلوبة والنهائية التي سنعود إليها.

رمز

التنفيذ في 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

التنفيذ في Java لـ Array Queries من أجل الضرب والاستبدال والمنتج

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

تحليل التعقيد

تعقيد الوقت

O (ن) أين "ن" هو عدد العناصر في المصفوفة. لكل استعلام O (N) الوقت مطلوب لأنه يتعين علينا اجتياز النطاق المعطى لنا بالكامل.

تعقيد الفضاء

O (ن) أين "ن" هو عدد العناصر في المصفوفة. نظرًا لأننا أنشأنا صفيفتين غير المدخلات ، فإن الخوارزمية لها تعقيد مساحة خطي.