주어진 범위에서 짝수 또는 홀수 확률에 대한 쿼리

난이도 하드
자주 묻는 질문 구글 하니웰 동네 짱
배열조회수 34

우리는 정렬 정수, q 쿼리 수. 각 쿼리에는 쿼리 유형을 정의하는 세 개의 정수가 포함됩니다. 즉, 0을 주면 주어진 범위에서 홀수를 선택할 확률을 찾아야 함을 의미합니다. 범위는 시작점과 끝점으로 정의됩니다. 이 특정 범위 내에서 모든 유형의 특정 쿼리. 각 쿼리에 대한 솔루션을 찾아야합니다. 각 쿼리는

TSE : T = 0을 제공했다면 주어진 배열 A에서 주어진 범위 (S : 시작점, E : 끝점)에서 짝수를 선택할 확률을 찾아야 함을 의미합니다.

TSE : T = 1을 주면 주어진 배열 A에서 주어진 범위 (S : 시작점, E : 끝점)에서 홀수를 선택할 확률을 찾아야 함을 의미합니다.

입력:

배열 [] = {2, 3, 4, 5, 6}

쿼리 1 : 1 1 3

쿼리 1 : 0 1 4

출력:

1/3

1/2

설명 :

우리는 쿼리에서 T = 1을 주었다는 것은 1과 3 범위에서 홀수를 선택할 확률을 찾아야 함을 의미합니다.

우리는 쿼리에서 T = 0을 주었다는 것은 1과 4 범위에서 짝수를 선택할 확률을 찾아야 함을 의미합니다.

주어진 범위에서 짝수 또는 홀수 확률에 대한 쿼리

암호알고리즘

  1. 주어진 배열과 크기가 같은 홀수와 짝수에 대해 두 개의 배열을 만듭니다. 두 배열의 첫 번째 요소를 0으로 초기화합니다.
  2. 배열을 가로 지르고 숫자가 홀수인지 확인한 다음 생성 한 oddNumber 배열의 값을 odd [i] + 1의 숫자로 채우고 우리가 생성 한 짝수 배열에 짝수 [i]를 입력하고 짝수가 발견되면 동일합니다. 홀수를 현재 홀수 evenNumber 배열에 저장하고 oddNumber 배열을 oddNumber 배열에 저장합니다.
  3. 질의 횟수까지 순회하여 오른쪽, 왼쪽, 1의 차이를 저장합니다.
  4. 확률을 찾기 위해 짝수 또는 홀수를 선택해야하는지 확인하고, 홀수이면 probab에 해당 값을 oddNumber [right]와 oddNumber [left – 1]의 차이로 저장합니다.
  5. 그렇지 않으면 짝수 [오른쪽]와 짝수 [왼쪽 – 1]의 차이로 probab에 값을 저장합니다.
  6. probab이 0보다 작거나 같은지 확인한 다음 0을 인쇄합니다. 그렇지 않으면 temp와 같으면 1을 인쇄합니다. Else는 셀 수있는 총 호의 수를 찾습니다.
  7. 가치 probab과 그 호의 수를 인쇄하십시오.

설명

우리는 홀수를위한 배열과 저장할 짝수를위한 배열을 만들 것입니다. 이제 배열을 탐색하여 배열 요소가 홀수인지 또는 홀수인지 찾아 볼 것입니다. 우리는 짝수를 oddNumber 배열에 저장할 것입니다. 그리고 evenNumber의 이전 값에서 evenNumber의 현재 값으로, 숫자가 짝수이면 동일하게 따릅니다. 그런 다음 홀수 값을 evenNumber 배열에 저장하고 oddNumber 배열의 이전 값을 현재 oddNumber의 현재 값에 저장합니다. 이 모든 것은 생성 된 배열의 숫자로 배열을 만들고 채우는 것입니다.

쿼리 유형, 왼쪽 및 오른쪽 지점을 범위로 가져 와서 차이를 얻습니다. 주어진 쿼리가 어떤 유형인지 찾을 수 있습니다. 1보다 크면 짝수를 선택할 확률을 알아 내기 위해 홀수를 선택해야합니다. 그렇지 않으면 범위 내에서 짝수의 확률을 찾을 수 있습니다. 만약 그것이 홀수이면 우리가 생성 한 oddNumber 배열의 차이와 짝수 확률, evenNumber의 차이를 얻을 것입니다. probab에 차이를 저장하고 probab이 0보다 작거나 같으면 0을 인쇄하고, probab이 k와 같으면 1을 인쇄합니다. 그렇지 않으면 총 호의 수를 찾아야합니다. 마지막으로 가치 probab과 favours를 인쇄하십시오.

실시

주어진 범위에서 짝수 또는 홀수 확률에 대한 쿼리를위한 C ++ 프로그램

#include<iostream>

using namespace std;

#define C 3

int getDivisor(int a, int b)
{
    if (a == 0 || b == 0)
        return 0;

    if (a == b)
        return a;

    if (a > b)
        return getDivisor(a - b, b);

    return getDivisor(a, b - a);
}

void solveQuery(int arr[], int n, int Q,int query[][C])
{
    int evenNumber[n + 1];
    int oddNumber[n + 1];
    evenNumber[0] = oddNumber[0] = 0;

    for (int i = 0; i < n; i++)
    {
        if (arr[i] & 1)
        {
            oddNumber[i + 1] = oddNumber[i] + 1;
            evenNumber[i + 1] = evenNumber[i];
        }
        else
        {
            evenNumber[i + 1] = evenNumber[i] + 1;
            oddNumber[i + 1] = oddNumber[i];
        }
    }
    for (int i = 0; i < Q; i++)
    {
        int right = query[i][2];
        int left = query[i][1];
        int T = query[i][0];

        int dif = right - left + 1;
        int probab;

        if (T)
            probab = oddNumber[right] - oddNumber[left - 1];
        else
            probab = evenNumber[right] - evenNumber[left - 1];

        if (!probab)
            cout << "0" << endl;

        else if (probab == dif)
            cout << "1" << endl;

        else
        {
            int div = getDivisor(probab, dif);
            cout << probab / div << "/" << dif / div << endl;
        }
    }
}

int main()
{
    int arr[] = { 2,3,4,5,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 2;
    int query[Q][C] = { { 1, 1, 3 },
        { 0, 1, 4 }
    };

    solveQuery(arr, n, Q, query);
    return 0;
}
1/3
1/2

주어진 범위에서 짝수 또는 홀수 확률에 대한 쿼리를위한 Java 프로그램

public class QueryProbability
{
    static int getDivisor(int a, int b)
    {
        if (a == 0 || b == 0)
            return 0;

        if (a == b)
            return a;

        if (a > b)
            return getDivisor(a - b, b);

        return getDivisor(a, b - a);
    }
    
    static void solveQuery(int []arr, int n, int Q, int [][]query)
    {
        int []evenNumber = new int[n + 1];
        int []oddNumber = new int[n + 1];
        evenNumber[0] = oddNumber[0] = 0;

        for (int i = 0; i < n; i++)
        {
            if ((arr[i] & 1) > 0)
            {
                oddNumber[i + 1] = oddNumber[i] + 1;
                evenNumber[i + 1] = evenNumber[i];
            }
            else
            {
                evenNumber[i + 1] = evenNumber[i] + 1;
                oddNumber[i + 1] = oddNumber[i];
            }
        }
        
        for (int i = 0; i < Q; i++)
        {
            int right = query[i][2];
            int left = query[i][1];
            int T = query[i][0];

            int dif = right - left + 1;
            int probab;
            if (T > 0)
                probab = oddNumber[right] - oddNumber[left - 1];
            else
                probab = evenNumber[right] - evenNumber[left - 1];

            if (probab <= 0)
                System.out.println("0");
            else if (probab == dif)
                System.out.println("1");

            else
            {
                int div = getDivisor(probab, dif);
                System.out.println(probab / div + "/" +dif / div);
            }
        }
    }
    
    static public void main (String[] args)
    {
        int []arr = { 2, 3, 4, 5, 6 };
        int n = arr.length;
        int Q = 2;
        int [][]query = { { 1, 1, 3 },
            { 0, 1, 4 }
        };

        solveQuery(arr, n, Q, query);
    }
}
1/3
1/2

주어진 범위에서 짝수 또는 홀수 확률 쿼리에 대한 복잡성 분석

시간 복잡성

O (q * n) 어디에 "Q" 쿼리 수이며 "엔" 배열의 요소 수입니다.

공간 복잡성

O (N) 어디에 "엔" 배열의 요소 수입니다.

참고

Translate »