แบบสอบถามอาร์เรย์สำหรับการแทนที่และผลิตภัณฑ์แบบทวีคูณ


ระดับความยาก ยาก
ถามบ่อยใน จังหวะอินเดีย เดอชอว์ Expedia Google
แถว ปัญหาการสืบค้น

ปัญหา“ Array Queries สำหรับการคูณการแทนที่และผลิตภัณฑ์” ระบุว่าคุณได้รับไฟล์ แถว of จำนวนเต็ม และจะมีคำค้นหาสามประเภทซึ่งคุณต้องแก้ไขคำถามประเภทต่อไปนี้:

ประเภทที่ 1: จะมีค่าสามค่าซ้ายขวาและตัวเลข X ในแบบสอบถามประเภทนี้คุณต้องคูณแต่ละองค์ประกอบของอาร์เรย์กับค่า X ในช่วง (ซ้ายขวา) รวม

แบบที่ 2: ประกอบด้วยค่าสามค่าซ้ายขวาเป็นช่วง คุณต้องแทนที่องค์ประกอบในช่วงที่กำหนดด้วยตัวเลข Y, 2Y, 3Y และอื่น ๆ

แบบที่ 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

คำอธิบาย

Type3 (2, 5) หลังผลคูณขององค์ประกอบทั้งหมดภายในช่วง 2 และ 5 ⇒ 2 * 3 * 4 * 5 = 120

Type3 (3, 5) หลังผลคูณขององค์ประกอบทั้งหมดภายในช่วง 3 และ 5 ⇒ 3 * 4 * 5 = 60

Type2 (1, 3, 1) หลังจากแทนที่แต่ละองค์ประกอบเป็น y, 2y และ 3y และอื่น ๆ ในช่วง 1 ถึง 3

Type1 (4, 5, 10) คูณแต่ละองค์ประกอบด้วย 10 ภายในช่วง 4 ถึง 5

Type3 (2, 4) หลังผลคูณขององค์ประกอบทั้งหมดภายในช่วง 3 และ 5 ⇒ 2 * 3 * 40 = 240

เอาต์พุต⇒ 3 ดังนั้นจะมีศูนย์ต่อท้าย 3 ตัวที่เราพบในแบบสอบถามประเภท 3 ดังนั้นจึงถูกพิมพ์ออกมา

Array Queries สำหรับการคูณการแทนที่และผลิตภัณฑ์

 

ขั้นตอนวิธี

  1. ประกาศสองอาร์เรย์เพื่อให้อาร์เรย์ทั้งสองเก็บจำนวนศูนย์ต่อท้ายที่สัมพันธ์กับตัวเลข 2 และ 5 ตามลำดับ
  2. ถ้าเราเรียก type1 ให้หาค่าศูนย์ต่อท้ายของ X ในรูปของ 2 และ 5
  3. สำรวจผ่านอาร์เรย์ภายในช่วงที่กำหนด คูณตัวเลขแต่ละตัวด้วยค่า X พร้อมกันเก็บค่าของศูนย์เป็นผลคูณของ 2 และ 5 ลงในอาร์เรย์ที่เราสร้างขึ้น ศูนย์ และ zeroesInFive.
  4. ถ้าเราเรียก type2 ให้หาค่าศูนย์ท้ายของ Y อีกครั้งในแง่ของ 2 และ 5
  5. จัดเก็บ Y ที่ตำแหน่งแรกของช่วง 2Y ในวินาทีและอื่น ๆ จัดเก็บจำนวนของศูนย์ต่อท้ายไปยัง zeroesInTwo และ zeroesInFive พร้อมกัน
  6. และสำหรับ type3 รับผลรวมของค่าทั้งหมดที่อยู่ในช่วงเป็น zeroesInTwo และ zeroesInFive และหาจำนวนขั้นต่ำของจำนวนศูนย์ในสองหรือจำนวนศูนย์ในห้า
  7. พิมพ์ค่าเป็นผลรวม

คำอธิบาย

เราได้รับอาร์เรย์จำนวนเต็มและแบบสอบถามสามประเภทเพื่อแก้ปัญหา หนึ่งในข้อความค้นหาบอกว่าคุณต้องคูณจำนวนภายในช่วง อีกอันบอกว่าคุณต้องแทนที่ตัวเลขบางตัว คนสุดท้ายบอกว่าคุณต้องหาผลคูณของตัวเลขที่อยู่ในช่วง จากนั้นในการดำเนินการแต่ละแบบสอบถามเราได้แยกฟังก์ชันทั้งสามซึ่งทำหน้าที่เป็นส่วนหนึ่งสำหรับแต่ละแบบสอบถามตามลำดับ จากนั้นเราจะหาค่าศูนย์ต่อท้าย ด้วยเหตุนี้เราจึงได้สร้างอาร์เรย์สองอาร์เรย์หนึ่งสำหรับในแง่ของ 2 และอีกอันคือสำหรับในแง่ของ 5

ในการแก้แบบสอบถามประเภทแรกเราจะได้รับหมายเลข X และช่วงในแง่ของจุดเริ่มต้นและจุดสิ้นสุด เพื่อหาค่าศูนย์ต่อท้ายที่สามารถเกิดขึ้นได้ เราจะตรวจสอบว่าตัวเลขที่ระบุมีศูนย์ต่อท้ายหรือไม่ จากนั้นรับจำนวนศูนย์ต่อท้ายเหล่านี้ สิ่งเดียวกันคือการทำกับศูนย์ในแง่ของห้า เราจะข้ามอาร์เรย์จากจุดเริ่มต้นของช่วงไปยังจุดสิ้นสุดของช่วง จากนั้นเราจะคูณค่า X กับแต่ละตัวเลขในขณะที่เคลื่อนที่ นอกจากนี้เราจะดำเนินการเพิ่มเติมในอาร์เรย์ที่เราสร้างขึ้นเพื่อจัดเก็บศูนย์ สิ่งเดียวกันคือการทำในแบบสอบถามประเภท 2 เราเพียงแค่ต้องแทนที่แต่ละองค์ประกอบด้วยตัวเลขที่กำหนดในรูปแบบของอนุกรม

ในการแก้ไขแบบสอบถามประเภทที่สามเราจะกำหนดค่าของ sumOfTwos และ sumOfFives ถึง 0 เราจะจัดเก็บค่าในตัวแปรที่เราสร้าง sumOfTwos และ sumOfFives จากนั้นเราจะค้นหาขั้นต่ำของ sumOfTwos และ sumOfFives นั่นจะเป็นคำตอบที่จำเป็นและเราจะกลับมา

รหัส

การใช้งานใน C ++ สำหรับ Array Queries สำหรับการคูณการแทนที่และผลิตภัณฑ์

#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 (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ สำหรับแต่ละแบบสอบถาม O (N) จำเป็นต้องใช้เวลาเนื่องจากเราต้องสำรวจช่วงทั้งหมดที่ให้กับเรา

ความซับซ้อนของอวกาศ

O (n) ที่ไหน “ n” คือจำนวนองค์ประกอบในอาร์เรย์ เนื่องจากเราได้สร้างอาร์เรย์สองอาร์เรย์นอกเหนือจากอินพุตอัลกอริทึมจึงมีความซับซ้อนของพื้นที่เชิงเส้น