આપેલ શ્રેણીમાં સમાન અથવા વિચિત્ર સંખ્યાની સંભાવના પર પ્રશ્નો


મુશ્કેલી સ્તર હાર્ડ
વારંવાર પૂછવામાં આવે છે Google હનીવેલ ઉબેર
અરે

અમે એક આપ્યો છે એરે પૂર્ણાંક, પ્રશ્નોની સંખ્યા. જ્યાં દરેક ક્વેરીમાં ત્રણ પૂર્ણાંકો હોય છે, જે ક્વેરીના પ્રકારને વ્યાખ્યાયિત કરે છે. આનો અર્થ એ છે કે જો આપણે 0 આપ્યું છે, તો તેનો અર્થ એ કે આપેલ શ્રેણીમાં વિચિત્ર નંબર પસંદ કરવાની સંભાવના આપણે શોધવી પડશે. જ્યાં શ્રેણી પ્રારંભિક બિંદુ અને અંતિમ બિંદુ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. કોઈપણ પ્રકારની વિશેષ ક્વેરીની આ વિશિષ્ટ શ્રેણીની અંદર. તમારે દરેક ક્વેરી માટે સમાધાન શોધવું પડશે. દરેક ક્વેરીના સ્વરૂપમાં હશે

TSE: જો તમે T = 0 આપ્યો છે, તો તેનો અર્થ એ છે કે આપેલ શ્રેણીમાં A આપેલ શ્રેણી (એસ: પ્રારંભિક પોઇન્ટ, E: સમાપ્ત બિંદુ) માં સમાન સંખ્યા પસંદ કરવાની સંભાવના શોધી કા haveવી પડશે.

TSE: જો તમે T = 1 આપ્યો છે, તો પછી તેનો અર્થ એ છે કે આપેલ એરે A માં આપેલ શ્રેણી (એસ: પ્રારંભિક પોઇન્ટ, E: સમાપ્ત બિંદુ) માં એક વિચિત્ર નંબર પસંદ કરવાની સંભાવના શોધવા પડશે.

ઉદાહરણ

ઇનપુટ:

એરે [] = {2, 3, 4, 5, 6}

ક્વેરી 1: 1 1 3

ક્વેરી 1: 0 1 4

આઉટપુટ:

1 / 3

1 / 2

સમજૂતી:

આપણે ક્વેરીમાં ટી = 1 આપ્યો છે, તેનો અર્થ એ કે આપણે 1 અને 3 શ્રેણીમાં એક વિચિત્ર નંબર પસંદ કરવાની સંભાવના શોધવી પડશે.

આપણે ક્વેરીમાં ટી = 0 આપ્યા છે, એટલે કે આપણે 1 અને 4 ની શ્રેણીમાં સમાન સંખ્યા પસંદ કરવાની સંભાવના શોધવી પડશે.

આપેલ શ્રેણીમાં સમાન અથવા વિચિત્ર સંખ્યાની સંભાવના પર પ્રશ્નો

અલ્ગોરિધમ

  1. વિચિત્ર સંખ્યાઓ અને સમાન સંખ્યાઓ માટે બે એરે બનાવો, આપેલ એરે જેટલા કદના. બંનેના એરેના પ્રથમ તત્વને 0 થી પ્રારંભ કરો.
  2. એરેને ટ્રverseવર કરો અને તપાસ કરો કે શું સંખ્યા વિચિત્ર છે તો પછી અમે odડ સંખ્યા [i] + 1 ની સંખ્યામાં બનાવેલ dડ નમ્બર એરેનું મૂલ્ય ભરો અને તે પણ એરેમાં અમે સંખ્યા પર બનાવ્યાં [i] અને જો સંખ્યા મળી તો પણ, વિચિત્ર સંખ્યાને વર્તમાન વિચિત્ર ઇવન નંબર એરેમાં સંગ્રહિત કરો, અને ઓડ નમ્બર એરેમાં ઓડ નંબર નંબર એરે.
  3. ક્વેરી સંખ્યા સુધીનો સમય પસાર કરો અને જમણા, ડાબી અને 1 નો તફાવત સ્ટોર કરો.
  4. સંભાવના શોધવા માટે જો આપણે પણ સંખ્યા અથવા વિચિત્ર નંબર પસંદ કરવાની છે કે કેમ તે તપાસો, જો કોઈ વિચિત્ર સંખ્યા હોય, તો પછી પ્રોબેબમાં મૂલ્યને ઓડનમ્બર [જમણે] અને ઓડનમ્બર [ડાબે - 1] ના તફાવત તરીકે સંગ્રહિત કરો.
  5. બાકી પ્રોવેબમાં વેવનમ્બર [જમણે] અને ઇવન નંબર [ડાબી - 1] ના તફાવત તરીકે મૂલ્ય સ્ટોર કરો.
  6. ચકાસણી કરો કે પ્રોબે 0 કરતા ઓછા અથવા બરાબર છે, પછી 0. છાપો. બાકી તે ટેમ્પની બરાબર છે, તો પછી 1 છાપો. બાકી, કુલ ગમતી તરફેણની કુલ સંખ્યા શોધો.
  7. મૂલ્ય પ્રોબે અને તે તરફેણની સંખ્યા છાપો.

સમજૂતી

આપણે બે એરે બનાવી રહ્યા છીએ એક વિચિત્ર નંબર માટે અને એક સ્ટોર કરવા માટે પણ સંખ્યા માટે. હવે, આપણે એરેને પસાર કરીશું અને શોધીશું કે એરે એલિમેન્ટ વિચિત્ર છે કે કેમ તે વિચિત્ર છે. અમે સમાન સંખ્યાને વિચિત્ર નંબર એરેમાં સ્ટોર કરીશું. ઇવનનમ્બરના વર્તમાન મૂલ્ય માટે ઇવન નંબર અગાઉના મૂલ્ય, સમાન હોય તો તેનું પાલન કરવું જો સંખ્યા સમાન હોય. પછી વિચિત્ર મૂલ્યને ઇવનમ્બર એરે અને ઓડ નમ્બર એરેના અગાઉના મૂલ્યને વર્તમાન ઓડનમ્બરના વર્તમાન મૂલ્યમાં સંગ્રહિત કરો. આ બધું ક્રમશ created બનાવેલ એરેમાં નંબરો સાથે એરે બનાવવા અને ભરવાનું છે.

ક્વેરીનો પ્રકાર, ડાબી અને જમણી બિંદુઓ શ્રેણી તરીકે મેળવો, તેમાં તફાવત મેળવો. આપણે આપેલ ક્વેરી કયા પ્રકારનું છે તે શોધીશું. જો તે 1 કરતા વધારે છે, તો પછી આપણે સમાન સંખ્યા પસંદ કરવાની સંભાવના શોધવા માટે એક વિચિત્ર સંખ્યા પસંદ કરવી પડશે. બાકી આપણે શ્રેણીમાં પણ સંખ્યાની સંભાવના શોધીશું. જો તે વિચિત્ર છે, તો પછી આપણે બનાવેલ ઓડ નમ્બર એરેનો તફાવત અને સમાન સંખ્યા સંભાવના, ઇવન નમ્બરનો તફાવત મેળવીશું. આપણે પ્રોબેબમાં તફાવત સંગ્રહિત કરીશું, અને જો પ્રોબાબ 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

આપેલ રેન્જમાં ઇવન અથવા ઓડ નંબરની સંભાવના પર ક્વેરીઝ માટે જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (ક્યૂ * એન) જ્યાં "ક્યૂ" પ્રશ્નોની સંખ્યા છે અને “એન” એરેમાં તત્વોની સંખ્યા છે

અવકાશ જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે.

સંદર્ભ