ਦਿੱਤੀਆਂ ਗਈਆਂ ਸੀਮਾਵਾਂ ਵਿਚ ਇਵ ਜਾਂ ਓਡ ਨੰਬਰ ਦੀ ਸੰਭਾਵਨਾ ਬਾਰੇ ਪ੍ਰਸ਼ਨ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਹਾਰਡ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਗੂਗਲ ਹਨੀਵੈੱਲ ਉਬੇਰ
ਅਰੇ

ਅਸੀਂ ਇੱਕ ਦਿੱਤਾ ਹੈ ਐਰੇ ਪੂਰਨ ਅੰਕ ਦੀ, ਕਿ quਰੀਆਂ ਦੀ ਕਿ q ਨੰਬਰ. ਜਿੱਥੇ ਹਰੇਕ ਪੁੱਛਗਿੱਛ ਵਿਚ ਤਿੰਨ ਪੂਰਨ ਅੰਕ ਹੁੰਦੇ ਹਨ, ਜੋ ਕਿ ਇਕ ਕਿਸਮ ਦੀ ਪੁੱਛਗਿੱਛ ਨੂੰ ਪ੍ਰਭਾਸ਼ਿਤ ਕਰਦੇ ਹਨ. ਇਸਦਾ ਅਰਥ ਇਹ ਹੈ ਕਿ ਜੇ ਅਸੀਂ 0 ਦਿੱਤਾ ਹੈ ਤਾਂ ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸਾਨੂੰ ਦਿੱਤੀ ਗਈ ਸੀਮਾ ਵਿੱਚ ਕਿਸੇ ਅਜੀਬ ਸੰਖਿਆ ਨੂੰ ਚੁਣਨ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਲੱਭਣਾ ਹੈ. ਜਿੱਥੇ ਸੀਮਾ ਨੂੰ ਇੱਕ ਸ਼ੁਰੂਆਤੀ ਬਿੰਦੂ ਅਤੇ ਇੱਕ ਅੰਤ ਬਿੰਦੂ ਦੇ ਤੌਰ ਤੇ ਪਰਿਭਾਸ਼ਤ ਕੀਤਾ ਗਿਆ ਹੈ. ਕਿਸੇ ਵੀ ਕਿਸਮ ਦੀ ਵਿਸ਼ੇਸ਼ ਪੁੱਛਗਿੱਛ ਦੀ ਇਸ ਵਿਸ਼ੇਸ਼ ਸੀਮਾ ਦੇ ਅੰਦਰ. ਤੁਹਾਨੂੰ ਹਰੇਕ ਪੁੱਛਗਿੱਛ ਲਈ ਹੱਲ ਲੱਭਣਾ ਪਏਗਾ. ਹਰ ਪੁੱਛਗਿੱਛ ਦੇ ਰੂਪ ਵਿੱਚ ਹੋਵੇਗੀ

ਟੀ ਐੱਸ ਈ: ਜੇ ਤੁਸੀਂ ਟੀ = 0 ਦਿੱਤਾ ਹੈ, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਦਿੱਤੀ ਗਈ ਰੇਂਜ ਏ ਵਿਚ ਦਿੱਤੇ ਗਏ ਸੀਮਾ (ਐਸ: ਅਰੰਭਕ ਪੁਆਇੰਟ, ਈ: ਅੰਤਮ ਪੁਆਇੰਟ) ਵਿਚ ਇਕ ਸਮ ਨੰਬਰ ਚੁਣਨ ਦੀ ਸੰਭਾਵਨਾ ਲੱਭਣੀ ਹੈ.

ਟੀ ਐਸ ਸੀ: ਜੇ ਤੁਸੀਂ ਟੀ = 1 ਦਿੱਤਾ ਹੈ, ਤਦ ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਦਿੱਤੀ ਗਈ ਰੇਂਜ ਏ ਵਿੱਚ ਦਿੱਤੀ ਗਈ ਸੀਮਾ (ਐੱਸ: ਅਰੰਭਕ ਬਿੰਦੂ, ਈ: ਅੰਤਮ ਪੁਆਇੰਟ) ਵਿਚ ਇਕ ਅਜੀਬ ਸੰਖਿਆ ਦੀ ਚੋਣ ਕਰਨ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਲੱਭਣਾ ਹੋਵੇਗਾ.

ਉਦਾਹਰਨ

ਇੰਪੁੱਟ:

ਐਰੇ [] = {2, 3, 4, 5, 6}

ਪ੍ਰਸ਼ਨ 1: 1 1 3

ਪ੍ਰਸ਼ਨ 1: 0 1 4

ਆਉਟਪੁੱਟ:

1 / 3

1 / 2

ਸਪਸ਼ਟੀਕਰਨ:

ਅਸੀਂ ਇੱਕ ਪੁੱਛਗਿੱਛ ਵਿੱਚ, ਟੀ = 1 ਦਿੱਤਾ ਹੈ, ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਸਾਨੂੰ 1 ਅਤੇ 3 ਦੇ ਸ਼ਮੂਲੀਅਤ ਵਿੱਚ ਇੱਕ ਅਜੀਬ ਸੰਖਿਆ ਨੂੰ ਚੁਣਨ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਲੱਭਣਾ ਹੈ.

ਅਸੀਂ ਇੱਕ ਪੁੱਛਗਿੱਛ ਵਿੱਚ, ਟੀ = 0 ਦਿੱਤਾ ਹੈ, ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸਾਨੂੰ 1 ਅਤੇ 4 ਦੇ ਸ਼ਮੂਲੀਅਤ ਵਿੱਚ ਇੱਕ ਵੀ ਸੰਖਿਆ ਦੀ ਚੋਣ ਕਰਨ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਲੱਭਣਾ ਹੈ.

ਦਿੱਤੀਆਂ ਗਈਆਂ ਸੀਮਾਵਾਂ ਵਿਚ ਇਵ ਜਾਂ ਓਡ ਨੰਬਰ ਦੀ ਸੰਭਾਵਨਾ ਬਾਰੇ ਪ੍ਰਸ਼ਨ

ਐਲਗੋਰਿਥਮ

  1. ਅਜੀਬ ਸੰਖਿਆਵਾਂ ਅਤੇ ਇੱਥੋ ਤਕ ਸੰਖਿਆਵਾਂ ਲਈ ਦੋ ਐਰੇ ਬਣਾਓ, ਇਕ ਅਕਾਰ ਦੇ ਦਿੱਤੇ ਗਏ ਐਰੇ ਵਾਂਗ. ਐਰੇ ਦੇ ਪਹਿਲੇ ਐਲੀਮੈਂਟ ਨੂੰ ਅਰੰਭ ਕਰੋ.
  2. ਐਰੇ ਨੂੰ ਟ੍ਰਾੱਰ ਕਰੋ ਅਤੇ ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਇਹ ਗਿਣਤੀ ਅਜੀਬ ਹੈ ਤਾਂ ਫਿਰ odਡ ਨੰਬਰ ਨੰਬਰ ਦੇ ਐਰੇ ਦਾ ਮੁੱਲ ਭਰੋ ਜੋ ਅਸੀਂ ਵਿਜਿਟ [i] + 1 ਦੀ ਸੰਖਿਆ ਵਿਚ ਬਣਾਏ ਹਨ ਅਤੇ ਇੱਥੋਂ ਤਕ ਕਿ ਅਰੇ ਨੂੰ ਵੀ ਅਸੀਂ ਨੰਬਰ ਤੇ ਬਣਾਇਆ ਹੈ [i] ਅਤੇ ਇਕੋ ਜੇ ਸੰਖਿਆ ਵੀ ਮਿਲ ਗਈ ਹੈ, ਅਜਿੱਖ ਨੰਬਰ ਨੂੰ ਮੌਜੂਦਾ ਅਨਿਸ਼ਤ ਈਵ ਨੰਬਰ ਐਰੇ ਵਿੱਚ ਰੱਖੋ, ਅਤੇ odਡ ਨੰਬਰ ਐਰੇ ਨੂੰ ਅਨਿਸ਼ਚਤ ਨੰਬਰ.
  3. ਪੁੱਛਗਿੱਛ ਦੀ ਗਿਣਤੀ ਤਕ ਦਾ ਸਫ਼ਰ ਕਰੋ, ਅਤੇ ਸੱਜੇ, ਖੱਬੇ ਅਤੇ 1 ਦੇ ਅੰਤਰ ਨੂੰ ਸਟੋਰ ਕਰੋ.
  4. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਸਾਨੂੰ ਸੰਭਾਵਨਾ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਇਕੋ ਜਿਹਾ ਨੰਬਰ ਜਾਂ ਅਜੀਬ ਸੰਖਿਆ ਨੂੰ ਚੁਣਨਾ ਹੈ, ਜੇ ਇਕ ਅਜੀਬ ਸੰਖਿਆ ਹੈ, ਤਦ ਪ੍ਰੋਬੇ ਵਿਚ ਮੁੱਲ ਨੂੰ umberਡਨੰਬਰ [ਸੱਜੇ] ਅਤੇ ਓਡਨੰਬਰ [ਖੱਬੇ - 1] ਦੇ ਅੰਤਰ ਦੇ ਤੌਰ ਤੇ ਸਟੋਰ ਕਰੋ.
  5. ਹੋਰ ਪ੍ਰੋਬੇ ਵਿੱਚ ਵੈਲਯੂ ਨੰਬਰ (ਸੱਜੇ] ਅਤੇ ਇੱਥੋਂ ਦੇ ਨੰਬਰ [ਖੱਬੇ - 1] ਦੇ ਅੰਤਰ ਦੇ ਰੂਪ ਵਿੱਚ ਵੈਲਯੂ ਨੂੰ ਸਟੋਰ ਕਰੋ.
  6. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਪ੍ਰੋਬ 0 ਤੋਂ ਘੱਟ ਹੈ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਹੈ, ਫਿਰ 0 ਪਰਿੰਟ ਕਰੋ. ਨਹੀਂ ਤਾਂ ਇਹ ਟੈਂਪ ਦੇ ਬਰਾਬਰ ਹੈ, ਫਿਰ 1. ਪਰਿੰਟ ਕਰੋ. ਨਹੀਂ ਤਾਂ ਉਨ੍ਹਾਂ ਸਾਰੇ ਪੱਖਪਾਤ ਦੀ ਸੰਖਿਆ ਪਤਾ ਕਰੋ ਜਿਹੜੀਆਂ ਗਿਣੀਆਂ ਜਾ ਸਕਦੀਆਂ ਹਨ.
  7. ਵੈਲਯੂ ਪ੍ਰੋਬੇ ਅਤੇ ਪੱਖ ਦੀ ਗਿਣਤੀ ਛਾਪੋ.

ਕਥਾ

ਅਸੀਂ ਦੋ ਐਰੇ ਬਣਾਉਣ ਜਾ ਰਹੇ ਹਾਂ ਇਕ ਅਜੀਬ ਸੰਖਿਆ ਲਈ ਅਤੇ ਇਕ ਇਵ ਨੰਬਰ ਲਈ ਸਟੋਰ ਕਰਨ ਲਈ. ਹੁਣ, ਅਸੀਂ ਐਰੇ ਨੂੰ ਪਾਰ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਅਤੇ ਇਹ ਲੱਭਣ ਜਾ ਰਹੇ ਹਾਂ ਕਿ ਐਰੇ ਐਲੀਮੈਂਟ ਅਜੀਬ ਹੈ ਜਾਂ ਭਾਵੇਂ ਇਹ ਅਜੀਬ ਹੈ. ਅਸੀ ਸੰਖਿਆ ਨੰਬਰ ਨੂੰ dਡ ਨੰਬਰ ਨੰਬਰ ਤੇ ਸਟੋਰ ਕਰਾਂਗੇ. ਇਵ ਨੰਬਰ ਦੀ ਮੌਜੂਦਾ ਵੈਲਯੂ ਦਾ ਈਵਨ ਨੰਬਰ ਪਿਛਲੀ ਵੈਲਯੂ ਦਾ ਵੀ ਪਾਲਣ ਕਰਨਾ ਹੈ, ਜੇ ਨੰਬਰ ਇਕੋ ਹੈ ਤਾਂ. ਫੇਰ ਅਜੀਬ ਮੁੱਲ ਨੂੰ ਵੀ ਨੰਬਰ ਨੰਬਰ ਐਰੇ ਅਤੇ ਓਡ ਨੰਬਰ ਨੰਬਰ ਐਰੇ ਦੇ ਪਿਛਲੇ ਮੁੱਲ ਨੂੰ ਮੌਜੂਦਾ ਓਡ ਨੰਬਰ ਦੇ ਮੌਜੂਦਾ ਮੁੱਲ ਵਿੱਚ ਸਟੋਰ ਕਰੋ. ਇਹ ਸਭ ਕ੍ਰਮਵਾਰ ਬਣਾਏ ਐਰੇ ਵਿਚ ਨੰਬਰਾਂ ਨਾਲ ਐਰੇ ਬਣਾਉਣ ਅਤੇ ਭਰਨਾ ਹੈ.

ਪੁੱਛਗਿੱਛ ਦੀ ਕਿਸਮ, ਖੱਬੇ ਅਤੇ ਸੱਜੇ ਪੁਆਇੰਟਾਂ ਨੂੰ ਸੀਮਾ ਦੇ ਰੂਪ ਵਿੱਚ ਲਿਆਓ, ਉਹਨਾਂ ਦਾ ਅੰਤਰ ਪਾਓ. ਸਾਨੂੰ ਦਿੱਤੀ ਗਈ ਪੁੱਛਗਿੱਛ ਕਿਸ ਕਿਸਮ ਦੀ ਹੈ ਇਹ ਪਤਾ ਲਗਾਵਾਂਗੇ. ਜੇ ਇਹ 1 ਤੋਂ ਵੱਧ ਹੈ, ਤਾਂ ਸਾਨੂੰ ਇਕ ਸੰਖਿਆ ਦੀ ਚੋਣ ਕਰਨ ਦੀ ਸੰਭਾਵਨਾ ਨੂੰ ਪਤਾ ਲਗਾਉਣ ਲਈ ਇਕ ਅਜੀਬ ਸੰਖਿਆ ਦੀ ਚੋਣ ਕਰਨੀ ਪਏਗੀ. ਨਹੀਂ ਤਾਂ ਅਸੀਂ ਇਕ ਸੀਮਾ ਦੇ ਅੰਦਰ ਵੀ ਸੰਭਾਵਿਤ ਸੰਖਿਆ ਦੀ ਸੰਭਾਵਨਾ ਪਾਵਾਂਗੇ. ਜੇ ਇਹ ਅਜੀਬ ਹੈ, ਤਾਂ ਸਾਨੂੰ createdਡ ਨੰਬਰ ਨੰਬਰ ਐਰੇ ਦਾ ਅੰਤਰ ਮਿਲੇਗਾ ਜੋ ਅਸੀਂ ਬਣਾਇਆ ਹੈ ਅਤੇ ਇਕੋ ਸੰਭਾਵਨਾ ਸੰਭਾਵਨਾ, ਇਵ ਨੰਬਰ ਦੇ ਅੰਤਰ ਦੇ ਨਾਲ. ਅਸੀਂ ਪ੍ਰੋਬੈਬ ਵਿਚ ਫਰਕ ਨੂੰ ਸਟੋਰ ਕਰਾਂਗੇ, ਅਤੇ ਜੇ ਪ੍ਰੋਬੈਬ 0 ਤੋਂ ਘੱਟ ਜਾਂ ਇਸ ਦੇ ਬਰਾਬਰ ਹੈ, ਅਸੀਂ 0 ਪਰਿੰਟ ਕਰਾਂਗੇ, ਨਹੀਂ ਤਾਂ ਜੇ ਇਹ ਪ੍ਰੋਬੇਬਲ ਕੇ ਦੇ ਬਰਾਬਰ ਹੈ, ਪਰਿੰਟ 1. ਹੋਰ ਸਾਨੂੰ ਐਵਾਰਡਾਂ ਦੀ ਕੁੱਲ ਗਿਣਤੀ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਅਤੇ ਅੰਤ ਵਿੱਚ, ਵੈਲਯੂ ਪ੍ਰੋਬੇ ਅਤੇ ਅਨੁਕੂਲਤਾ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰੋ.

ਲਾਗੂ

ਸੀ .+ ਪ੍ਰੋਗਰਾਮ ਦਰਸਾਏ ਗਏ ਸੀਮਾਵਾਂ ਵਿਚ ਇਵ ਜਾਂ ਓਡ ਨੰਬਰ ਦੀ ਸੰਭਾਵਨਾ ਬਾਰੇ ਪੁੱਛਗਿੱਛ ਲਈ

#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

ਜਾਵਾਂ ਪ੍ਰੋਗਰਾਮ ਦਿਤੇ ਗਏ ਸੀਮਾਵਾਂ ਵਿਚ ਇਵ ਜਾਂ ਓਡ ਨੰਬਰ ਦੀ ਸੰਭਾਵਨਾ ਬਾਰੇ ਪੁੱਛਗਿੱਛ ਲਈ

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

ਨਿਰਧਾਰਤ ਸੀਮਾਵਾਂ ਵਿੱਚ ਇਵ ਜਾਂ ਓਡ ਨੰਬਰ ਦੀ ਸੰਭਾਵਨਾ ਬਾਰੇ ਪੁੱਛਗਿੱਛ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਕਿ * * ਐਨ) ਜਿੱਥੇ ਕਿ "Q" ਕਿeriesਰੀਆਂ ਦੀ ਗਿਣਤੀ ਹੈ ਅਤੇ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਹੇ (n) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.

ਹਵਾਲਾ