שאילתות מערך להכפלת תחליפים ומוצר


רמת קושי קשה
נשאל לעתים קרובות קדנס הודו דה שו Expedia Google
מערך בעיית שאילתות

הבעיה "שאילתות מערך להכפלות, החלפות ומוצרים" קובעת כי ניתנת לך מערך 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

הסבר

סוג 3 (2, 5), לאחר תוצר של כל האלמנטים בטווח 2 ו -5 and 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. אם אנו קוראים ל- type1, קבל את האפסים הנגררים של X במונחים של 2 ו- 5.
  3. חצה את המערך בטווח נתון. הכפל כל מספר עם ערך X. במקביל, אחסן את ערך האפסים כמכפל של 2 ו- 5 במערך שיצרנו עבורו zeroesInTwo ו zeroesInFive.
  4. אם אנו קוראים לסוג 2, קבל שוב את האפסים הנגררים של Y, במונחים של 2 ו -5.
  5. אחסן את ה- Y במיקום הראשון של הטווח, 2Y במקום השני וכן הלאה. אחסן בו זמנית את ספירת האפסים הנגררים לאפסיםInTwo ו- zeroesInFive.
  6. ולגבי סוג 3, קבל את סכום כל הערכים הנמצאים בטווח באפסיםInTwo ו- zeroesInFive, וגלה את המינימום של ספירת האפסים בשניים או ספירת אפסים בחמישה.
  7. הדפס את הערך בסכום.

הסבר

אנו מקבלים מערך שלם ושלושה סוגים של שאילתות לפתרון. אחת השאלות אומרת שעליך להכפיל מספר כלשהו בטווח. השני אומר שאתה צריך להחליף כמה מספרים. האחרון אומר שאתה צריך למצוא את תוצר המספרים בטווח. ואז כדי לבצע כל אחת מהשאילתות ביצענו בנפרד את שלוש הפונקציות המבצעות את החלק שלהן עבור כל שאילתה בהתאמה. ואז נגלה את האפסים הנגררים. לשם כך יצרנו שני מערכים אחד נועד מבחינת 2, והשני נועד מבחינת 5.

כדי לפתור את סוג השאילתה הראשונה, נקבל מספר X וטווח מבחינת נקודת ההתחלה ונקודת הסיום. כדי לגלות את האפסים הנגררים שיכולים להתרחש. נגלה אם למספר הנתון יש אפסים נגררים. ואז קבל ספירה של אפסים נגררים אלה. אותו דבר הוא לעשות עם האפסים במונחים של חמישה. נעבור את המערך, מנקודת ההתחלה של הטווח ועד לנקודת הסיום של הטווח. אז נכפיל את הערך X עם כל מספר תוך כדי מעבר. אנו גם נבצע בו זמנית את התוספת על המערך שאנו יוצרים לאחסון אפסים. אותו הדבר הוא לעשות בשאילתת סוג 2, אנחנו רק צריכים להחליף כל אלמנט במספר הנתון, בצורה של סדרה.

כדי לפתור את שאילתת סוג שלוש, נגדיר את הערך של sumOfTwos ו sumOfFives עד 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 עבור שאילתות מערך להכפלות, החלפות ומוצרים

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" הוא מספר האלמנטים במערך. מכיוון שיצרנו שני מערכים פרט לקלט, לאלגוריתם יש מורכבות שטח ליניארית.