乗算置換と製品の配列クエリ


難易度 ハード
よく聞かれる ケイデンスインド DEショウ エクスペディア Googleポリシー
配列 クエリの問題

問題「乗算、置換、および積の配列クエリ」には、 配列 of 整数 そして、次のタイプのクエリを解決する必要があるXNUMXつのタイプのクエリがあります。

タイプ1:左、右のXNUMXつの値と数値Xがあります。このタイプのクエリでは、配列の各要素に範囲(左、右)の値Xを掛ける必要があります。

タイプ2:範囲として左右の2つの値で構成されます。 指定された範囲の要素を番号Y、3Y、XNUMXYなどに置き換える必要があります。

タイプ3:範囲として左右に3つの値があります。 指定された範囲内のすべての要素の積を見つける必要があります。 数が多くなる可能性があるため。 すべてのTypeXNUMXクエリで後続ゼロの総数をカウントする必要があります。

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)、各要素を2〜3の範囲でy、1y、3yなどに置き換えた後

Type1(4、5、10)、10から4の範囲内で各要素に5を掛けます

Type3(2、4)、3と5の範囲内のすべての要素の積の後⇒2* 3 * 40 = 240

出力⇒3、つまり、タイプ3クエリで見つかった末尾のゼロが合計3つあるので、出力されます。

乗算、置換、および積の配列クエリ

 

アルゴリズム

  1. 2つの配列を宣言して、両方の配列がそれぞれ5番とXNUMX番に関連する後続ゼロの数を格納するようにします。
  2. type1を呼び出す場合は、2と5に関してXの後続ゼロを取得します。
  3. 指定された範囲内で配列をトラバースします。 各数値に値Xを掛けます。同時に、ゼロの値を2と5の倍数として作成した配列に格納します。 zeroesInTwo 及び ゼロズインファイブ.
  4. type2を要求している場合は、2と5に関して、Yの後続ゼロを再度取得します。
  5. Yを範囲の最初の位置に格納し、2YをXNUMX番目の位置に格納します。 末尾のゼロの数をzeroesInTwoとzeroesInFiveに同時に保存します。
  6. また、type3の場合、zeroesInTwoとzeroesInFiveの範囲内にあるすべての値の合計を取得し、XNUMXつのゼロの数またはXNUMXつのゼロの数の最小値を見つけます。
  7. 値の合計を出力します。

説明

整数配列と2種類のクエリが与えられます。 クエリの5つは、範囲内のいくつかの数値を乗算する必要があることを示しています。 もうXNUMXつは、いくつかの番号を置き換える必要があると言っています。 最後のXNUMXつは、範囲内の数値の積を見つける必要があることを示しています。 次に、各クエリを実行するために、クエリごとにそれぞれの役割を果たすXNUMXつの関数を個別に作成しました。 次に、後続のゼロを見つけます。 そのために、XNUMXつの配列を作成しました。XNUMXつはXNUMXに関するもので、もうXNUMXつはXNUMXに関するものです。

最初のタイプのクエリを解決するために、開始点と終了点に関して数値Xと範囲が与えられます。 発生する可能性のある後続ゼロを見つけるため。 与えられた数に後続のゼロがあるかどうかを調べます。 次に、これらの後続ゼロの数を取得します。 同じことは、2の観点からゼロを扱うことです。 範囲の開始点から終了点まで、配列をトラバースします。 次に、トラバース中に値Xに各数値を乗算します。 また、ゼロを格納するために作成した配列に対して同時に加算を実行します。 同じことがタイプXNUMXクエリで行うことです。各要素を、一連の形式で指定された番号に置き換える必要があります。

タイプXNUMXのクエリを解決するために、次の値を設定します。 sumOfTwos 及び sumOfFives 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) where 「n」 配列内の要素の数です。 与えられた範囲全体をトラバースする必要があるため、クエリごとにO(N)時間が必要です。

スペースの複雑さ

O(N) where 「n」 配列内の要素の数です。 入力以外にXNUMXつの配列を作成したため、アルゴリズムには線形空間の複雑さがあります。