与えられた範囲での偶数または奇数の確率に関するクエリ


難易度 ハード
よく聞かれる Google ハニーウェル ユーバー
配列

私たちは与えました 配列 整数の、qクエリの数。 各クエリには、クエリのタイプを定義する0つの整数が含まれています。 これは、XNUMXを指定した場合、指定された範囲で奇数を選択する確率を見つける必要があることを意味します。 範囲が開始点と終了点として定義されている場合。 任意のタイプの特定のクエリのこの特定の範囲内。 各クエリの解決策を見つける必要があります。 各クエリは次の形式になります

TSE:T = 0を指定した場合、指定された配列Aで指定された範囲(S:開始点、E:終了点)で偶数を選択する確率を見つける必要があることを意味します。

TSE:T = 1を指定した場合、指定された配列Aの指定された範囲(S:開始点、E:終了点)で奇数を選択する確率を見つける必要があることを意味します。

入力:

array [] = {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つの配列を作成します。 両方の配列の最初の要素をXNUMXに初期化します。
  2. 配列をトラバースし、数値が奇数かどうかを確認してから、作成したoddNumber配列の値をodd [i] + 1の数に入力し、作成した偶数配列に偶数[i]に入力し、偶数が見つかった場合は同じにします。奇数を現在の奇数のevenNumber配列に格納し、oddNumber配列をoddNumber配列に格納します。
  3. クエリ回数までトラバースし、右、左、1の差を保存します。
  4. 確率を見つけるために偶数または奇数を選択する必要があるかどうかを確認し、奇数の場合は、その値をoddNumber [right]とoddNumber [left –1]の差としてprobabに格納します。
  5. それ以外の場合は、evenNumber [right]とevenNumber [left –1]の差として値をprobabに格納します。
  6. 確率が0以下かどうかを確認してから、0を出力します。それ以外の場合は、tempに等しい場合は、1を出力します。それ以外の場合は、カウントできる好意の総数を見つけます。
  7. 値probabとその好意の数を印刷します。

説明

奇数用と偶数用のXNUMXつの配列を作成して格納します。 次に、配列を走査して、配列要素が奇数であるかどうか、または奇数であるかどうかを確認します。 偶数を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) where "Q" クエリの数と 「n」 配列内の要素の数です

スペースの複雑さ

O(N) where 「n」 配列の要素数です。

参照