다중 교체 및 제품에 대한 어레이 쿼리

난이도 하드
자주 묻는 질문 케이던스 인도 드 쇼 Expedia 구글
배열 쿼리 문제조회수 17

"배열, 교체 및 제품에 대한 배열 쿼리"문제는 사용자에게 정렬 of 정수 다음과 같은 유형의 쿼리를 해결해야하는 세 가지 유형의 쿼리가 있습니다.

유형 1 : 왼쪽, 오른쪽 및 숫자 X의 세 값이 있습니다.이 유형의 쿼리에서는 배열의 각 요소를 범위 (왼쪽, 오른쪽)의 값 X에 포함하여 곱해야합니다.

유형 2 : 왼쪽, 오른쪽 범위의 세 값으로 구성됩니다. 주어진 범위의 요소를 숫자 Y, 2Y, 3Y 등으로 바꿔야합니다.

유형 3 : 범위로 왼쪽과 오른쪽에 두 개의 값이 있습니다. 주어진 범위 내의 모든 요소의 곱을 찾아야합니다. 숫자가 클 수 있기 때문에. 모든 Type3 쿼리에서 후행 XNUMX의 총 수를 계산해야합니다.

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 개의 후행 XNUMX이 있으므로 인쇄됩니다.

곱하기, 교체 및 제품에 대한 어레이 쿼리

 

암호알고리즘

  1. 두 배열이 각각 숫자 2와 5에 상대적인 후행 XNUMX의 수를 저장하도록 두 배열을 선언합니다.
  2. type1을 호출하는 경우 2와 5를 기준으로 X의 후행 XNUMX을 가져옵니다.
  3. 주어진 범위 내에서 배열을 탐색합니다. 각 숫자에 값 X를 곱합니다. 동시에 2의 값을 5와 XNUMX의 배수로 우리가 만든 배열에 저장합니다. 제로인투제로인파이브.
  4. type2를 호출하는 경우 2와 5를 기준으로 Y의 후행 XNUMX을 다시 가져옵니다.
  5. 범위의 첫 번째 위치에 Y를 저장하고 두 번째에 2Y를 저장합니다. 후행 XNUMX의 개수를 zeroesInTwo 및 zeroesInFive에 동시에 저장합니다.
  6. 그리고 type3의 경우 XNUMXesInTwo 및 zeroesInFive 범위에있는 모든 값의 합계를 구하고 XNUMX에서 XNUMX의 개수 또는 XNUMX에서 XNUMX의 개수의 최소값을 찾습니다.
  7. 합계로 값을 인쇄하십시오.

설명

정수 배열과 풀어야 할 세 가지 유형의 쿼리가 제공됩니다. 쿼리 중 하나는 범위 내에서 일부 숫자를 곱해야한다고 말합니다. 다른 하나는 숫자를 바꿔야한다고 말합니다. 마지막은 범위 내에서 숫자의 곱을 찾아야한다고 말합니다. 그런 다음 각 쿼리를 수행하기 위해 각 쿼리에 대해 해당 부분을 수행하는 세 가지 기능을 별도로 만들었습니다. 그런 다음 후행 2을 찾을 것입니다. 이를 위해 두 개의 배열을 만들었습니다. 하나는 5를위한 것이고 다른 하나는 XNUMX를위한 것입니다.

첫 번째 유형의 쿼리를 해결하기 위해 시작점과 끝점 측면에서 숫자 X와 범위가 제공됩니다. 발생할 수있는 후행 2을 확인합니다. 주어진 숫자에 뒤에 XNUMX이 있는지 알아낼 것입니다. 그런 다음 이러한 후행 XNUMX의 개수를 가져옵니다. 같은 일이 XNUMX의 관점에서 XNUMX을 사용하는 것입니다. 범위의 시작점에서 범위의 끝점까지 배열을 순회합니다. 그런 다음 횡단하는 동안 X 값에 각 숫자를 곱합니다. 또한 XNUMX을 저장하기 위해 생성 한 배열에 대한 추가 작업도 동시에 수행합니다. 유형 XNUMX 쿼리에서도 동일한 작업을 수행합니다. 각 요소를 일련의 형태로 주어진 숫자로 대체하면됩니다.

유형 XNUMX 쿼리를 해결하기 위해 다음 값을 설정합니다. 합계합계 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) 어디에 "엔" 배열의 요소 수입니다. 입력이 아닌 두 개의 배열을 만들었으므로 알고리즘은 선형 공간 복잡성을 갖습니다.

Translate »