Multiplits အစားထိုးခြင်းနှင့်ထုတ်ကုန်အတွက် Array Queries


ခက်ခဲအဆင့် ခိုင်မာသော
မကြာခဏမေးတယ် Cadence အိန္ဒိယ DE Shaw Expedia Google
အခင်းအကျင်း ပြeryနာပြ.နာ

ပြmultipနာ“ Multiplite, အစားထိုးခြင်းနှင့်ထုတ်ကုန်အတွက် Array Queries” သည်သင့်အားပေးထားသည်ဟုဖော်ပြထားသည် အခင်းအကျင်း of ကိန်း အောက်ပါမေးခွန်း ၃ မျိုးရှိလိမ့်မည်။ ထိုနေရာတွင်အောက်ပါအမျိုးအစားများကိုသင်ဖြေရှင်းရမည် -

Type 1: ဘယ်ဘက်၊ ညာနှင့်တန်ဖိုးနံပါတ်သုံးခုရှိလိမ့်မည်။ ဤရှာဖွေမှုတွင်သင်သည် array ၏ element တစ်ခုစီကိုအကွာအဝေး (ဘယ်၊ ညာ) တွင်ပါ ၀ င်သောတန်ဖိုးသို့မြှောက်ရမည်။

အမျိုးအစား ၂ - ဘယ်ဘက်မှာတန်ဖိုး ၃ ခုပါဝင်တယ်။ ပေးထားသောအကွာအဝေးရှိ element များကိုနံပါတ်များ Y, 2Y, 2Y စသည်တို့ဖြင့်အစားထိုးရန်လိုအပ်သည်။

အမျိုးအစား ၃ - အကွာအဝေးအနေဖြင့်ဘယ်ဘက်နှင့်ညာဘက်တွင်တန်ဖိုးနှစ်ခုရှိသည်။ သငျသညျပေးထားသောအကွာအဝေးအတွင်းရှိအားလုံးဒြပ်စင်များ၏ထုတ်ကုန်ကိုရှာဖွေရန်ရှိသည်။ အရေအတွက်ကကြီးမားနိုင်ပါတယ်ကတည်းက။ 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

ရှင်းလင်းချက်

Type3 (2, 5), အကွာအဝေး 2 နှင့် 5 ⇒ 2 * 3 * 4 * 5 = 120 အတွင်းရှိအားလုံးသောဒြပ်စင်များ၏ထုတ်ကုန်ပြီးနောက်

Type3 (3, 5), အကွာအဝေး 3 နှင့် 5 * 3 * 4 * 5 = 60 အတွင်းအားလုံးဒြပ်စင်များ၏ထုတ်ကုန်ပြီးနောက်

Type2 (၁၊ ၃၊ ၁)၊ element တစ်ခုစီအား y၊ 1y နှင့် 3y များနှင့်အစားထိုးပြီးနောက် 1 မှ 2 အတွင်းတွင်ရှိသည်။

Type1 (4, 5, 10) သည် element တစ်ခုချင်းစီကို 10 မှ 4 အထိ 5 နှင့်မြှောက်ပါ

Type3 (2, 4), အကွာအဝေး 3 နှင့် 5 ⇒ 2 * 3 * 40 = 240 အတွင်းအားလုံးဒြပ်စင်များ၏ထုတ်ကုန်ပြီးနောက်

ရလဒ် ၃၊ ဒါကြောင့်စုစုပေါင်းနောက်ကွယ်သုည (၃) ခုရှိလိမ့်မယ်၊ အမျိုးအစား (၃) မေးမြန်းချက်မှာတွေ့ပြီ၊ ဒါကိုပုံနှိပ်တယ်။

များပြားခြင်း၊ အစားထိုးခြင်းနှင့်ထုတ်ကုန်အတွက် Array Query

 

algorithm

  1. Array နှစ်ခုစလုံးကိုကြေငြာပါက arrays နှစ်ခုလုံးသည်နံပါတ် 2 နှင့် 5 နှင့်သက်ဆိုင်သော zeroing အရေအတွက်ကိုသိမ်းဆည်းလိမ့်မည်။
  2. အကယ်၍ ကျွန်ုပ်တို့သည် type1 ကိုခေါ်ဆိုပါက၊ X နှင့် 2 ၏စည်းမျဉ်းများအရ X ၏အောက်တွင်ရှိသောသုညများကိုရယူပါ။
  3. ပေးထားသောအကွာအဝေးအတွင်းခင်းကျင်းမှတဆင့်ဖြတ်သန်း။ နံပါတ်တစ်ခုစီကိုတန်ဖိုး X ဖြင့်မြှောက်ပါ။ တစ်ပြိုင်နက်တည်း၊ သုည၏တန်ဖိုးကို ၂ နှင့် ၅ အမြှောက်အဖြစ်ကျွန်ုပ်တို့ဖန်တီးခဲ့သောခင်းကျင်းထဲထည့်ပါ။ သုည နှင့် သုည.
  4. အကယ်၍ ကျွန်ုပ်တို့သည် type2 ကိုခေါ်ဆိုပါက၊ 2 နှင့် 5 ၏စည်းမျဉ်းများအရ Y ၏အောက်တွင်ဖော်ပြထားသောသုညတန်ဖိုးကိုထပ်မံယူပါ။
  5. Y ကိုအကွာအဝေး၏ပထမဆုံးအနေအထားတွင်၊ 2Y ကိုဒုတိယနှင့်စသည်ဖြင့်သိုလှောင်ထားပါ။ တစ်ပြိုင်နက်တည်းတွင်သုည၏သုညအရေအတွက်ကို zeroesInTwo နှင့် zeroesInFive သို့သိမ်းဆည်းထားပါ။
  6. type3 အတွက်တန်ဖိုးသုညInTwoနှင့် zeroesInFive အကွာအဝေးရှိတန်ဖိုးအားလုံး၏ပေါင်းလဒ်ကိုရယူပါ။ သုညအနိမ့်အမြင့်နှစ်ခု၏နှစ်ခုသို့မဟုတ်ငါးလုံးတွင်သုညအရေအတွက်ရှာပါ။
  7. ပေါင်းလဒ်အတွက်တန်ဖိုး print ထုတ်ပါ။

ရှင်းလင်းချက်

ကျွန်တော်တို့အားလုံးအတွက်ကိန်းသေနံပါတ်သုံးခုနှင့်ဖြေရှင်းရန်မေးခွန်း ၃ ခုကိုပေးထားသည်။ မေးမြန်းမှုတစ်ခုအရသင်သည်အချို့သောနံပါတ်များကိုအကွာအဝေးအတွင်းမြှောက်ရန်လိုသည်။ နောက်တစ်ခုကတော့နံပါတ်တွေအစားထိုးရမယ်လို့ပြောတယ်။ နောက်ဆုံးတစ်ခုကသင်သည်နံပါတ်များထုတ်ကုန်ကိုအကွာအဝေးအတွင်းရှာဖွေရမည်ဟုပြောခဲ့သည်။ ထို့နောက်မေးမြန်းမှုတစ်ခုချင်းစီကိုလုပ်ဆောင်ရန်ကျွန်ုပ်တို့သည်သီးခြားလုပ်ဆောင်ချက်သုံးခုကိုသီးခြားစီပြုလုပ်ပြီးမေးမြန်းမှုတစ်ခုစီအတွက်သူတို့၏အပိုင်းကိုလုပ်ဆောင်သည်။ ထိုအခါကျွန်ုပ်တို့သည်နောက်ကွယ်မှသုညရှာတွေ့ပါလိမ့်မယ်။ ဒီအတွက်ကျွန်တော်တို့က arrays နှစ်ခုကိုတစ်ခုဖန်တီးလိုက်တယ်၊ တစ်ခုက 2 အတွက်ဖြစ်တယ်။ နောက်တစ်ခုက 5 အတွက်ဖြစ်တယ်။

ပထမ ဦး ဆုံးမေးမြန်းမှုပုံစံကိုဖြေရှင်းရန်ကျွန်ုပ်တို့အားနံပါတ် X နှင့်အကွာအဝေးကိုစမှတ်နှင့်အဆုံးသတ်အမှတ်ပေးလိမ့်မည်။ ဖြစ်ပျက်နိုင်သည့်နောက်ကွယ်မှသုညထွက်ရှာရန်။ ပေးထားတဲ့နံပါတ်မှာဒီသုညရဲ့သုညရှိသလားဆိုတာငါတို့ရှာတွေ့လိမ့်မယ်။ ပြီးရင်ဒီသုညသုညအရေအတွက်ကိုရမယ်။ တူညီတဲ့အရာကသုညနဲ့ ၅ ခုပါ။ ကျွန်ုပ်တို့သည်အကွာအဝေး၏စမှတ်မှသည်အကွာအဝေး၏အဆုံးအထိဖြစ်သည်။ ပြီးရင်ဖြတ်သွားတဲ့အခါမှာနံပါတ်တစ်ခုစီကို X တန်ဖိုးမြှောက်ပါမယ်။ သုညများကိုသိုလှောင်ရန်ကျွန်ုပ်တို့ဖန်တီးသည့်ခင်းကျင်းချက်အပေါ်တစ်ပြိုင်နက်တည်းထပ်မံလုပ်ဆောင်မည်။ တူညီတဲ့အရာက type 2 query ကိုလုပ်ခြင်းဖြစ်သည်။ element တစ်ခုစီကိုပေးထားသောနံပါတ်ဖြင့်စီးရီးပုံစံဖြင့်အစားထိုးရုံသာလိုအပ်သည်။

အမျိုးအစားသုံးခုမေးမြန်းမှုကိုဖြေရှင်းရန်ကျွန်ုပ်တို့သည်တန်ဖိုးကိုသတ်မှတ်မည် မင်္ဂလာပါ နှင့် sumOfFives to 0. ကျွန်ုပ်တို့သည် sumOfTwos နှင့် sumOfFives ကိုဖန်တီးထားသော variable တွင်တန်ဖိုးကိုသိမ်းဆည်းလိမ့်မည်။ သို့ဖြစ်လျှင် sumOfTwos နှင့် sumOfFives တို့၏အနိမ့်ဆုံးကိုကျွန်ုပ်တို့ရှာဖွေလိမ့်မည်။ ဒါကကျနော်တို့ပြန်လာလိမ့်မည်လိုအပ်သောနှင့်နောက်ဆုံးအဖြေကိုဖြစ်လိမ့်မည်။

ကုဒ်

များပြားခြင်း၊ အစားထိုးခြင်းနှင့်ထုတ်ကုန်များအတွက် Array Query များအတွက် 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

များပြားခြင်း၊ အစားထိုးခြင်းနှင့်ထုတ်ကုန်အတွက် Array Query များအတွက် Java တွင်အကောင်အထည်ဖော်ခြင်း

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” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ စုံစမ်းမှုတစ်ခုစီအတွက် O (N) အချိန်လိုအပ်သည်၊ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့အားပေးထားသောအကွာအဝေးတစ်ခုလုံးကိုဖြတ်ကျော်ရန်လိုသောကြောင့်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array အတွင်းရှိ element အရေအတွက်ဖြစ်သည်။ ကျနော်တို့ input ကိုထက်အခြား Array ကိုနှစ်ခုဖန်တီးကတည်းက, algorithm ကို linear အာကာသရှုပ်ထွေးရှိပါတယ်။