მასივის მოთხოვნები გამრავლებული ჩანაცვლებისა და პროდუქტისთვის


Რთული ტური Hard
ხშირად ეკითხებიან კადენს ინდოეთი დე შოუ Expedia Google
Array შეკითხვის პრობლემა

პრობლემა "მასივის მოთხოვნები გამრავლების, ჩანაცვლებისა და პროდუქტისთვის" აცხადებს, რომ თქვენ გეძლევათ მასივი 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 ⇒ 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-ის ჯერადი ჩვენს მიერ შექმნილ მასივში zeroesInTwo და zeroesInFive.
  4. თუ ტიპი 2-ს მოვუწოდებთ, ისევ მიიღეთ Y- ის ჩამორჩენილი ნულები, 2-ის და 5-ის თვალსაზრისით.
  5. შეინახეთ Y დიაპაზონის პირველ პოზიციაზე, 2Y მეორეზე და ა.შ. ერთდროულად შეინახეთ ნულოვანი უკანა რიცხვების ნულოვანიInTwo და zeroesInFive.
  6. და ტიპის 3-ისთვის, მიიღეთ ყველა მნიშვნელობის ჯამი, რომლებიც დიაპაზონშია zeroesInTwo და 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) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. თითოეული მოთხოვნისთვის საჭიროა O (N) დრო, რადგან ჩვენ უნდა გადავკვეთოთ მოცემული დიაპაზონის მთელი ნაწილი.

სივრცის სირთულე

O (n) სადაც "ნ" არის მასივის ელემენტების რაოდენობა. მას შემდეგ, რაც შეყვანის გარდა შევქმენით ორი მასივი, ალგორითმს აქვს ხაზოვანი სივრცის სირთულე.